二分模板

普通二分查找模板

  1.  public int search(int[] nums, int target) {
  2.       int left = 0;
  3.       int right = nums.length - 1;
  5.       while (left <= right) {
  6.         int mid = (left + right) / 2;
  7.         if (nums[mid] == target) return mid;
  8.         else if (nums[mid] < target) left = mid +1;
  9.         else right = mid-1;
  10.       }
  11.       return -1;
  12.     }

lower_bound

查找lower_bound（第一个>=target的数），不存在返回nums.length

  1.   public int search02(int[] nums, int target) {
  2.     int left = 0;
  3.     int right = nums.length;
  4.     while (left < right) {
  5.       int mid = (left + right) / 2;
  6.       if (nums[mid] >= target) {
  7.         right = mid;
  8.       } else {
  9.         left = mid + 1;
  10.       }
  11.     }
  12.     return right;
  13.   }

  • 另外一种写法

    1. public int bsearch(int[] a, int n, int value) {
    2.   int low = 0;
    3.   int high = n - 1;
    4.   while (low <= high) {
    5.     int mid = low + ((high - low) >> 1);
    6.     if (a[mid] >= value) {
    7.       if ((mid == 0) || (a[mid - 1] < value)) { // 判断是不是第一个
    8.         return mid;
    9.       } else {
    10.         high = mid - 1;
    11.       }
    12.     } else {
    13.       low = mid + 1;
    14.     }
    15.   }
    16.   return n;
    17. }

    upper_bound

    查找最后一个<=target的数，不存在返回-1

    1. // 查找最后一个小于等于target的元素
    2. public int search03(int[] nums, int target) {
    3.   int left = -1;
    4.   int right = nums.length - 1;
    5.   while (left < right) {
    6.     int mid = (left + right + 1) / 2;
    7.     if (nums[mid] <= target) {
    8.       left = mid;
    9.     } else {
    10.       right = mid - 1;
    11.     }
    12.   }
    13.   return right;
    14. }

  • 模板二

    1. // 二分变体4：查找最后一个小于等于给定值的元素
    2. public int bsearch7(int[] a, int n, int value) {
    3.   int low = 0;
    4.   int high = n - 1;
    5.   while (low <= high) {
    6.     int mid = low + ((high - low) >> 1);
    7.     if (a[mid] > value) {
    8.       high = mid - 1;
    9.     } else {
    10.       if ((mid == n - 1) || (a[mid + 1] > value)) {
    11.         return mid;
    12.       } else {
    13.         low = mid + 1;
    14.       }
    15.     }
    16.   }
    17.   return -1;
    18. }

    实战

    153. 寻找旋转排序数组中的最小值

    image.png

  • 二分条件，数组整体不是递增的，可以分为递增的二分条件，参考lower_bound

    1. public int findMin(int[] nums) {
    2.     int left = 0;
    3.     int right = nums.length - 1;
    5.     // 查找第一个小于等于right的数字
    6.     while (left < right) {
    7.       int mid = (left + right) / 2;
    8.       if (nums[mid] <= nums[right]) {
    9.         right = mid; // 答案是mid或者在mid左边
    10.       } else {
    11.         left = mid + 1; // 答案在mid右边
    12.       }
    13.     }
    14.     return nums[right];
    15.   }

    34. 在排序数组中查找元素的第一个和最后一个位置

    给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target，返回 [-1, -1]。

  1. public int[] searchRange(int[] nums, int target) {
  2.       // 第一个比target - 1大的下标也就是第一个target的下标
  3.       int left = search(nums, target - 1);
  4.       // 第一个比target大的下标-1,也就是最后一个target的下标
  5.       int right = search(nums, target) - 1;
  6.       if (left <= right && nums[left] == target) {
  7.         return new int[]{left, right};
  8.       }
  9.       return new int[]{-1, -1};
  10.     }
  12.     // 查找第一个比target大的下标
  13.     private int search(int[] nums, int target) {
  14.       int left = 0;
  15.       int right = nums.length;
  17.       while (left < right) {
  18.         int mid = (left + right) / 2;
  19.         if (nums[mid] > target) {
  20.           right = mid; // 答案是right或者在right左边
  21.         } else {
  22.           left = mid + 1; // 答案在mid右边
  23.         }
  24.       }
  25.       // 如果找不到比target大的下标，说明数组元素都比target小，将nums.length返回
  26.       return right;
  27.     }

69. x 的平方根

  1. public int mySqrt(int x) {
  3.       int left = 1;
  4.       int right = x;
  6.       while (left < right) {
  7.         int mid = (left + right + 1) / 2;
  8.         if (mid * mid <= x) {
  9.           // 答案是mid或者mid的右边
  10.           left = mid;
  11.         } else {
  12.           right = mid - 1;
  13.         }
  14.       }
  15.       return right;
  16.     }

三分查找

image.png
image.png

162. 寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。 给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

  1. public int findPeakElement(int[] nums) {
  2.       int left = 0;
  3.       int right = nums.length - 1;
  5.       while (left < right) {
  6.         int lmid = (left + right) / 2;
  7.         int rmid = lmid + 1;
  8.         if (nums[lmid] <= nums[rmid]) { // 峰值一定在lmid的右边
  9.           left = lmid + 1;
  10.         } else { // 峰值一定在rmid的左边
  11.           right = rmid - 1;
  12.         }
  13.       }
  14.       // 这里返回left或者right都行，循环的终止条件是left == right
  15.       return right;
  16.     }

二分答案

image.png

410. 分割数组的最大值

给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。 设计一个算法使得这 m 个子数组各自和的最大值最小。

  1. class Solution {
  3.     public int splitArray(int[] nums, int m) {
  4.       int left = 0;
  5.       int right = 0;
  6.       for (int num : nums) {
  7.         left = Math.max(left, num);
  8.         right += num;
  9.       }
  11.       while (left < right) {
  12.         int mid = left + (right - left) / 2;
  13.         if (validate(nums, m, mid)) { // 满足条件，size为mid能满足分成m段
  14.           right = mid;
  15.         } else {
  16.           left = mid +1;
  17.         }
  18.       }
  19.       return right;
  20.     }
  22.     // 对于一个数字size，判断是否数字每段和不超过size的情况下，能分成m段
  23.     private boolean validate(int[] nums, int m, int size) {
  24.       int box = 0;
  25.       int count = 1;
  27.       for (int num : nums) {
  28.         if (box + num <= size) { // 这一段还可以继续放
  29.           box += num;
  30.         } else { // 需要开启新的一段
  31.           count++;
  32.           box = num;
  33.         }
  34.       }
  35.       return count <= m;
  36.     }
  37.   }

实战

剑指 Offer II 068. 查找插入位置

给定一个排序的整数数组 nums 和一个整数目标值 target ，请在数组中找到 target ，并返回其下标。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

  • 查找第一个大于target的元素