搜索一个元素

最基础版本（搜索闭区间）

  1. int binarySearch(int[] arr, int target) {
  2.         int n = arr.length;
  3.         int left = 0, right = n - 1;
  5.         while(left <= right) {
  6.             int mid = (left + right) / 2;
  7.             if(arr[mid] == target) {
  8.                 return mid;
  9.             }else if(arr[mid] < target) {
  10.                 left = mid + 1;
  11.             }
  12.             else if(arr[mid] > target) {
  13.                 right = mid - 1;
  14.             }
  15.         }
  16.         return -1;
  17.     }

搜索左边界（左闭右开区间），在该区间搜索一个值的左边界，如果不存在返回-1

  1. // 在给定的单调区间里，找到target的左边界
  2. // 此处还有另一种理解方式，
  3. // 例如 arr = {1, 2, 3, 3, 4}
  4. // target = 3 的左边界的下标(left_bound)代表着 “小于target的数有left_bound个”
  6. // 考虑搜索区间的划分，对于区间[left, right)，
  7. // 下一次搜索的区间为 [left, mid) 或 [mid+1, right)
  8. // 其中[left, mid) 包含了 [left, mid-1]
  10. // 对于target不存在arr中的情况的处理
  11. // 1.如果 target > arr[n-1]，则 left == n
  12. // 2.如果 arr[i] < target < arr[j],其中 0 <= i < j < n
  13. //   有 arr[left] != left
  15. int left_bound(int[] arr, int target) {
  16.         int n = arr.length;
  17.         int left = 0, right = n;  // 注意：此处为左闭右开区间[left, right)
  19.         while (left < right) {  // 注意
  20.             int mid = (left + right) / 2;
  21.             if (arr[mid] == target) {
  22.                 right = mid;  // 缩小右边界，往左边搜索
  23.             } else if (arr[mid] < target) {
  24.                 left = mid + 1;
  25.             } else if (arr[mid] > target) {
  26.                 right = mid;
  27.             }
  28.         }
  30.         // 注意
  31.         if(left == n)
  32.             return -1;
  33.         return arr[left] == target ? left : -1;
  34.     }

搜索右边界（左开右闭区间），在该区间搜索一个值的右边界，如果不存在返回-1

  1. // 在给定的单调区间里，找到target的右边界
  2. // 此处还有另一种理解方式，
  3. // 例如 arr = {1, 2, 3, 3, 4}
  4. // target = 3 的右边界的下标(right_bound)代表着 “小于或等于target的数有left_bound个”
  6. // 此处和搜索左边界相同
  7. // 考虑搜索区间的划分，对于区间[left, right)，
  8. // 下一次搜索的区间为 [left, mid) 或 [mid+1, right)
  9. // 其中[left, mid) 包含了 [left, mid-1]
  11. // 对于target不存在arr中的情况的处理
  12. // 1.如果 target < arr[n-1]，则 left == 0
  14. // 为什么在搜索到target的情况下返回值是left-1?
  15. // 因为搜索的出口是left==right,而且我们对left的更新必定是mid+1,
  16. // 也就是说，当退出循环时，arr[left]必定不等于target,而arr[left-1]可能等于target
  17. // 这就需要我们去判断了
  20. int right_bound(int[] arr, int target) {
  21.         int n = arr.length;
  22.         int left = 0, right = n; // 注意
  24.         while(left < right) {
  25.             int mid = (left + right) / 2;
  26.             if(arr[mid] == target) { 
  27.                 left = mid + 1;   // 注意
  28.             }else if(arr[mid] < target) {
  29.                 left = mid + 1;
  30.             }else if(arr[mid] > target) {
  31.                 right = mid;
  32.             }
  33.         }
  35.         // 注意
  36.         if(left == 0)
  37.             return -1;
  38.         return arr[left-1] == target ? left -1 : -1;
  39.     }

搜索边界

左边界

image.png

// 搜索左侧边界
int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            // 当找到 target 时，收缩右侧边界
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left;
}

右边界

image.png

// 搜索右侧边界
int right_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            // 当找到 target 时，收缩左侧边界
            left = mid + 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left - 1;
}