1、返回查找值的随机索引

搜索区间是 [left, right] 的左闭右闭写法 int binary_search(int[] nums, int target) { int left = 0, right = nums.length - 1; while(left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if(nums[mid] == target) { // 找到该值直接返回其索引 return mid; } } // 没有找到 return -1; } 搜索区间是 [left, right) 的左闭右开写法 def binary_search(list_a, target): left = 0 right = len(list_a) while left < right: mid = (left + right) // 2 if list_a[mid] == target: return mid elif list_a[mid] < target: left = mid + 1 elif list_a[mid] > target: right = mid return -1 # 没找到

2、返回查找值的左边界索引

搜索区间是 [left, right] 的左闭右闭写法 int left_bound(int[] nums, int target) { int left = 0, right = nums.length - 1; // 搜索区间为 [left, right] while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { // 搜索区间变为 [mid+1, right] left = mid + 1; } else if (nums[mid] > target) { // 搜索区间变为 [left, mid-1] right = mid - 1; } else if (nums[mid] == target) { // 收缩右侧边界 // 如果存在target，那right最后必定是target左边界的位置减1 right = mid - 1; } } // 检查出界情况 // left == right + 1跳出循环 if (left == nums.length) return -1; return nums[left] == target ? left : -1; } 搜索区间是 [left, right) 的左闭右开写法 int left_bound(int[] nums, int target) { if (nums.length == 0) return -1; int left = 0; int right = nums.length; // 注意 while (left < right) { // 注意 int mid = (left + right) / 2; if (nums[mid] == target) { right = mid; } else if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid; // 注意 } } // target 比所有数都大 if (left == nums.length) return -1; // 类似之前算法的处理方式 return nums[left] == target ? left : -1; }

3、返回查找值的右边界索引

搜索区间是 [left, right] 的左闭右闭写法 int right_bound(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { // 如果存在target，那right最后就是右边界 // 如果不存在target，right是第一个小于target的值 right = mid - 1; } else if (nums[mid] == target) { // 这里改成收缩左侧边界即可 left = mid + 1; } } // left = right + 1 跳出循环,所以left最大值为nums_length // 所以left就不用判断溢出了 return nums[left-1] == target ? left-1 : -1; } 搜索区间是 [left, right) 的左闭右开写法 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) / 2; if (nums[mid] == target) { left = mid + 1; // 注意 } else if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { // 如果存在target, 那right最后是target右边界加1的位置 right = mid; } } // left==right时跳出循环， right的最大值为nums_length // 输出值为left-1不用判断溢出 return nums[left-1] == target ? left-1 : -1; }

4、总结一下两种写法的区别

while里面的条件用 ‘<’ 还是 '<= '。right的更新用 ‘mid - 1’ 还是 ‘mid’。对于查找左边界来说无论哪种写法都需要判断索引溢出，就算你用right来返回最后值，也要判断right是否小于0。返回随机索引和右边界索引不用判断索引溢出。

5、鸣谢

参考博客在此