一直以来，搞不清楚关于二分查找的边界问题，不是这里越界，就是那里越界，调试很久也可能A不了，今天，来总结一下关于二分查找
【LeetCode:34. 在排序数组中查找元素的第一个和最后一个位置】
1. 查找特定值
对于查找特定值来说，算是二分法的模板题目吧。
// 常规二分 public int erFen(int[] nums, int target) { int left = 0; int right = nums.length - 1; while (left <= right) { int mid = (right - left) / 2 + left; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } } return -1; }
2. 左侧边界
主要来求一个有序数组中，有重复的数字，让你去找重复数字最左边的边界或者第一个大于该数字的
- 还是原来的二分套路
- 当我们遇到目标值target时，向左进行偏移
right = mid - 1 - 最后结束的时候，我们对left的值进行一下判断
left >= nums.length || nums[left] != target，防止越界
// 左边界二分 // 如果当前遇到该值,则往左跑,right = mid - 1; public int leftErFen(int[] nums, int target) { int left = 0; int right = nums.length - 1; while (left <= right) { int mid = (right - left) / 2 + left; if (nums[mid] == target) { right = mid - 1; } else if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } } // 如果退出循环了，也就是left = right + 1 // 判断下越界了不 if (left >= nums.length || nums[left] != target) { return -1; } return left; }
3. 右侧边界
主要来求一个有序数组中，有重复的数字，让你去找重复数字最右边的边界
- 还是原来的二分套路
- 当我们遇到目标值target时，向右进行偏移
left = mid + 1 - 最后结束的时候，我们对right的值进行一下判断
right < 0 || nums[right] != target，防止越界
// 右界二分 // 如果当前遇到该值,则往左跑,right = mid - 1; public int rightErFen(int[] nums, int target) { int left = 0; int right = nums.length - 1; while (left <= right) { int mid = (right - left) / 2 + left; if (nums[mid] == target) { left = mid + 1; } else if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } } // 如果退出循环了，也就是left = right + 1 // 判断下越界了不 if (right < 0 || nums[right] != target) { return -1; } return right; }
