二分查找详解

二分查找框架

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

分析二分查找的一个技巧是：不要出现 else，而是把所有情况用 else if 写清楚，这样可以清楚地展现所有细节。

基本的二分搜索

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

逻辑分析

  1. 因为我们初始化 right = nums.length - 1
  2. 所以决定了我们的「搜索区间」是 [left, right]
  3. 所以决定了 while (left <= right)
  4. 同时也决定了 left = mid+1 和 right = mid-1
  6. 因为我们只需找到一个 target 的索引即可
  7. 所以当 nums[mid] == target 时可以立即返回

寻找左侧边界的二分搜索

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

逻辑分析

  1. 因为我们初始化 right = nums.length
  2. 所以决定了我们的「搜索区间」是 [left, right)
  3. 所以决定了 while (left < right)
  4. 同时也决定了 left = mid + 1 和 right = mid
  6. 因为我们需找到 target 的最左侧索引
  7. 所以当 nums[mid] == target 时不要立即返回
  8. 而要收紧右侧边界以锁定左侧边界

寻找右侧边界的二分查找

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

逻辑分析

  1. 因为我们初始化 right = nums.length
  2. 所以决定了我们的「搜索区间」是 [left, right)
  3. 所以决定了 while (left < right)
  4. 同时也决定了 left = mid + 1 和 right = mid
  6. 因为我们需找到 target 的最右侧索引
  7. 所以当 nums[mid] == target 时不要立即返回
  8. 而要收紧左侧边界以锁定右侧边界
  10. 又因为收紧左侧边界时必须 left = mid + 1
  11. 所以最后无论返回 left 还是 right，必须减一