1、二分法

二分法，需要注意mid 的取值，以及while中的等于号

1.1、搜索查找位置

力扣

  1.     public int searchInsert(int[] nums, int target) {
  2.         int low = 0, high = nums.length - 1;
  3.         int mid;
  4.         while (low <= high) { 
  5.             mid = low + (high-low)/2;
  6.             // System.out.println("a -- mid:" +(low+ (low + high) / 2));
  7.             // System.out.println("b -- mid:" + (mid));
  8.             if (nums[mid]>=target) high = mid - 1;
  9.             else low = mid + 1;
  10.         }
  11.         return low;
  12.     }

在上述中的数组中如果存在数字会直接返回结果，在while中可以不加等于号，当数组中不存在时，最后一次循环结果low = right ，且 mid = low 因此也可改造成下列程序：

  1. //简单的二分查找
  2. if (nums == null || nums.length == 0) {
  3.     return 0;
  4. }
  5. //小知识点： java数组的最大长度为int的最大值
  6. int left = 0;
  7. int right = nums.length - 1;
  8. while (left < right) {
  9.     int mid = (left + right) / 2;
  10.     if (target == nums[mid]) {
  11.         return mid;
  12.     } else if (target < nums[mid]) {
  13.         right = mid - 1;
  14.     } else {
  15.         left = mid + 1;
  16.     }
  17. }
  18. //此时left = right
  19. return target <= nums[left] ? left : left + 1;
  20. }

1.2、搜索二维矩阵

常规方法：分两次，分别是对列和行分别用二分法查找

  1. public boolean searchMatrix(int[][] matrix, int target) {
  2.         int m = matrix.length, n = matrix[0].length;
  3.         boolean res = false;
  4.         int low = -1,high  = m-1; //左开右闭的原则
  5.         while (low < high) {
  6.             int mid = low + (high - low+1) / 2;
  7.             if (matrix[mid][0]<=target) low= mid;
  8.             else high=mid-1;
  9.         }
  10.         if(low<0) return false;
  11.         System.out.println(low);
  12.         int left = 0, right = n - 1;
  13.         while (left <= right) {
  14.             int mid = left + (right - left) / 2;
  15.             if (matrix[low][mid]<target) left = mid + 1;
  16.             else if (matrix[low][mid]>target) right = mid - 1;
  17.             else return true;
  18.         }
  19.         return res;
  20.     }

一次拼接法：根据数组性质，将每一行的末尾与下一行进行拼接 并且将下标映射到原矩阵的行与列上

  1. class Solution {
  2.     public boolean searchMatrix(int[][] matrix, int target) {
  3.         int m = matrix.length, n = matrix[0].length;
  4.         int low = 0, high = m * n - 1;
  5.         while (low <= high) {
  6.             int mid = (high - low) / 2 + low;
  7.             int x = matrix[mid / n][mid % n]; //下标映射
  8.             if (x < target) {
  9.                 low = mid + 1;
  10.             } else if (x > target) {
  11.                 high = mid - 1;
  12.             } else {
  13.                 return true;
  14.             }
  15.         }
  16.         return false;
  17.     }
  18. }

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

力扣

可以直接套用二分法查找模板，当找到目标元素时，进行左右遍历，找到边界

  1.     public int[] searchRange(int[] nums, int target) {
  2.         int[] res = new int[]{-1, -1};
  3.         int left = 0, right = nums.length - 1;
  4.         while (left <= right) {
  5.             int mid = (left + right) / 2;
  6.             if (target == nums[mid]) {
  7.                 left = mid;
  8.                     // System.out.println(mid);
  9.                 while (mid>=0 && nums[mid] == target) {
  10.                     mid--;
  11.                 }
  12.                 res[0] = mid + 1;
  13.                 while (left<nums.length && nums[left] == target) {
  14.                     left++;
  15.                 }
  16.                 res[1] = left - 1;
  17.                 return res;
  18.             } else if (target < nums[mid]) {
  19.                 right = mid - 1;
  20.             } else {
  21.                 left = mid + 1;
  22.             }
  23.         }
  24.         return res;
  25.     }

左右分别求解

···java