二分查找(变体)代码框架

二分查找(变体)代码框架

1.说明

前面介绍了​​二分查找代码框架​​​, 查找的都是与target相同的数， 本文介绍的二分查找变体， 查找的是正好大于或者小于target的数， 即要找的数target不存在， 希望返回满足一定要求的数。

2.查找正好大于target的元素

这是​​二分查找代码框架​​​中, 查找左侧边界代码框架的变体， 当target不存在时， 得到的索引恰好是比target大的最小元素的索引， 即nums数组中第1个大于target的元素索引。

public static int leftBound(int[] nums, int target) { int left = 0; int right = nums.length - 1; // 下面的两个判断可省略，最终结果会覆盖这两种情况 // target比最小的元素还小，那索引为0的元素正好比target大 if (target < nums[left]) { return 0; } // target比最大的元素还大，则-1表示没有比target大的元素了 if (target > nums[right]) { return -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) { // 不能返回，锁定左边界，继续缩小右边界 right = mid - 1; } // 上面的"right = mid - 1;"代码体相同， // 判断条件可以合并为else if (nums[mid] >= target) } return left;}

3.查找正好小于target的元素

这是​​二分查找代码框架​​​中, 查找右侧边界代码框架的变体, 当target不存在时， 得到的索引恰好是比target小的最大元素的索引， 即nums数组中最后一个小于target的元素索引。

public static int rightBound(int[] nums, int target) { int left = 0; int right = nums.length - 1; // 下面的两个判断可省略，最终结果会覆盖这两种情况 // target比最小的元素还小，则-1表示没有比target小的元素了 if (target < nums[left]) { return -1; } // target比最大的元素还大，那索引为nums.length-1的元素正好比target小 if (target > nums[right]) { return right; } 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) { // 不能返回，锁定右边界，继续缩小左边界 left = mid + 1; } // 上面的"left = mid + 1;"代码体相同， // 判断条件可以合并为else if (nums[mid] <= target) } return right;}

4.二分查找(变体)代码框架优化

如下代码优化后非常简洁， 适合在实际项目中使用， 但是不推荐记忆下面的代码框架， 因为合并了很多实现细节， 不利于分析和理解， 还是推荐记忆上面的原始版本。

4.1.查找左侧边界变体优化

public static int leftBoundAdvance(int[] nums, int target) { int left = 0; int right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return left;}

4.2.查找右侧边界变体优化

public static int rightBoundAdvnce(int[] nums, int target) { int left = 0; int right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] <= target) { left = mid + 1; } else { right = mid - 1; } } return right;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。