有序数组 数组中无重复元素

704. 二分查找

  1. class Solution {
  2.     public int search(int[] nums, int target) {
  3.         int left = 0;
  4.         int right = nums.length - 1; // 注意
  6.         while(left <= right) {
  7.             int mid = left + (right - left) / 2;
  8.             if(nums[mid] == target)
  9.                 return mid;
  10.             else if (nums[mid] < target)
  11.                 left = mid + 1; // 注意
  12.             else if (nums[mid] > target)
  13.                 right = mid - 1; // 注意
  14.         }
  15.         return -1;
  16.     }
  17. }
  18. // 详细解析参见：
  19. // https://labuladong.github.io/article/?qno=704

力扣34题

  1.     /**
  2.      * 范围查询规律
  3.      * 初始化:
  4.      *   int left = 0;
  5.      *   int right = nums.length - 1;
  6.      * 循环条件
  7.      *   left <= right
  8.      * 右边取值
  9.      *   right = mid - 1
  10.      * 左边取值
  11.      *   left = mid + 1
  12.      * 查询条件
  13.      *   >= target值, 则 nums[mid] >= target时, 都减right = mid - 1
  14.      *   >  target值, 则 nums[mid] >  target时, 都减right = mid - 1
  15.      *   <= target值, 则 nums[mid] <= target时, 都加left = mid + 1
  16.      *   <  target值, 则 nums[mid] <  target时, 都加left = mid + 1
  17.      * 结果
  18.      *   求大于(含等于), 返回left
  19.      *   求小于(含等于), 返回right
  20.      * 示例(求> 或 >=)
  21.      *     private int search(int[] nums, int target) {
  22.      *         int left = 0;
  23.      *         int right = nums.length - 1;
  24.      *         while (left <= right){
  25.      *             int mid = (right - left) / 2 + left;
  26.      *             if (nums[mid] 查询条件 target){
  27.      *                 right = mid - 1;
  28.      *             } else {
  29.      *                 left = mid + 1;
  30.      *             }
  31.      *         }
  32.      *         return left(根据查询条件确认);
  33.      *     }
  34.      * 核心思想: 要找某个值, 则查找时遇到该值时, 当前指针(例如right指针)要错过它, 让另外一个指针(left指针)跨过他(体现在left <= right中的=号), 则找到了
  35.      */
  37. 作者：chendragon
  38. 链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/er-fen-cha-zhao-tong-yong-gui-lu-gu-ding-g93u/
  39. 来源：力扣（LeetCode）
  40. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

示例

  2.     /**
  3.      * 找数组中第一个 >= 目标值的索引
  4.      * 没找到则返回数组长度值
  5.      * 思路:
  6.      *   大于等于都满足, 则不能取right值, 只能取与left相关的
  7.      *   由于可以最大值都没有 >= 目标值, 故left要在遍历过程中达到 left > right
  8.      *   故循环结束条件 left <= right
  9.      *   left要大于right, 则nums[mid] >= target时 right = mid - 1, 是right降到小于目标值的位置, 然后left跨过去
  10.      *   left 固定必须为 mid + 1
  11.      * 没找到则返回数组长度值
  12.      */
  13.     public static int searchGeTarget(int[] nums, int target){
  14.         int left = 0;
  15.         int right = nums.length - 1;
  16.         while (left <= right){
  17.             int mid = (right - left) / 2 + left;
  18.             if (nums[mid] >= target){
  19.                 right = mid - 1;
  20.             } else {
  21.                 left = mid + 1;
  22.             }
  23.         }
  24.         return left;
  25.     }
  27.     /**
  28.      * 找数组中第一个 > 目标值的索引
  29.      * 没找到则返回数组长度值
  30.      */
  31.     public static int searchGtTarget(int[] nums, int target){
  32.         int left = 0;
  33.         int right = nums.length - 1;
  34.         while (left <= right){
  35.             int mid = (right - left) / 2 + left;
  36.             if (nums[mid] > target){
  37.                 right = mid - 1;
  38.             } else {
  39.                 left = mid + 1;
  40.             }
  41.         }
  42.         return left;
  43.     }
  45.     /**
  46.      * 找数组第一个 <= 目标值的索引(4,4,4,4)的右边界
  47.      * 没有则返回-1
  48.      */
  49.     public static int searchLeTarget(int[] nums, int target){
  50.         int left = 0;
  51.         int right = nums.length - 1;
  52.         while (left <= right){
  53.             int mid = (right - left) / 2 + left;
  54.             if (nums[mid] > target){
  55.                 right = mid - 1;
  56.             } else {
  57.                 left = mid + 1;
  58.             }
  59.         }
  60.         return right;
  61.     }
  63.     /**
  64.      * 找数组第一个 < 目标值的索引(4,4,4,4,5)的右边界5
  65.      * 没有则返回-1
  66.      */
  67.     public static int searchLtTarget(int[] nums, int target){
  68.         int left = 0;
  69.         int right = nums.length - 1;
  70.         while (left <= right){
  71.             int mid = (right - left) / 2 + left;
  72.             if (nums[mid] >= target){
  73.                 right = mid - 1;
  74.             } else {
  75.                 left = mid + 1;
  76.             }
  77.         }
  78.         return right;
  79.     }

34题代码

  1. class Solution {
  2.     /**
  3.      * 二分查找
  4.      */
  5.     public int[] searchRange(int[] nums, int target) {
  6.         //寻找左边界(这里寻找第一个 >= target的索引)
  7.         int leftIndex = search(nums, target);
  8.         if (leftIndex >= nums.length || nums[leftIndex] != target){
  9.             return new int[]{-1, -1};
  10.         }
  11.         //寻找右边界(这里寻找第一个 >= target+1的索引)
  12.         int rightIndex = search(nums, target + 1);
  13.         return new int[]{leftIndex, rightIndex - 1};
  14.     }
  16.     /**
  17.      * 寻找第一个>=目标值的索引, 找不到则返回数组长度
  18.      */
  19.     private int search(int[] nums, int target) {
  20.         int left = 0;
  21.         int right = nums.length - 1;
  22.         while (left <= right){
  23.             int mid = (right - left) / 2 + left;
  24.             if (nums[mid] >= target){
  25.                 right = mid - 1;
  26.             } else {
  27.                 left = mid + 1;
  28.             }
  29.         }
  30.         return left;
  31.     }
  32. }