📢 ：二分查找法的区间判断
📢 ：当我们在写二分查找的题目的时候（这里以leetcode的704. 二分查找，为例），常常会因为区间的选择而疑惑，是应该选择
while(left < right)；,还是while(left <= right);,应该写成lright = mid;,还是right = mid - 1;答案是都可以，这分别是区间的左闭右闭还是左闭右开，
- 上面是LeetCode上的题目，以下也是围绕着这道题来讲述的 ：
一，✨左闭右闭 ：
- 左闭右闭的意思是说我们判断的有序数组的区间，如果设数组长度为numsSize，定义：
int left = 0; int right = numSize - 1;
那就说我们判断的区间是[left , right]。
- 接下来的代码是 ：
while (left <= right) { }
- 如何判断写 **<还是<=**呢？
我们思考一下边界情况，当数组为 ： [1],此时 left = 0 , right = 0 ,此时还需要进入循环（原因参考完整代码，不进入循环只能返回-1或者需要单独解决这种情况），所以可以有 left = 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 { return mid; } }
当nums[mid] < taeget时，说明正确的目标值所在的区间是右半部分，由于nums[mid] != taeget;
所以下一次的搜索范围应该不包含nums[mid]，所以 left = mid + 1;
right = mid - 1的原因同上 ；
- 左闭右闭的完整代码如下 ；
int search(int* nums, int numsSize, int target){ int left = 0 ; int right = numsSize - 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 { return mid; } } return -1; }
二，✨左闭右开
- 左闭右开的区间为 [left , right ),不包括right ,代码和左闭右闭也会有所不同 ，定义如下 ：
int left = 0; int right = numsSize;
因为不包含right，所以right = numsSize; 而不是 ： right = numsSize - 1 ;
- 接下来的代码是 ：
while (left < right) { }
同上，我们假设数组为 [1] , 此时left = 0; right = 1; 此时已经到达了边界，但是left不会等于right了，所以代码为：left < right;
- 接下来的代码是 ：
while (left < right) { int mid = left + (right - left) / 2 ; if(nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid ; } else { return mid; } }
- left 取值的原因同上；
- 当 nums[mid] > target ，包含目标值的范围在区间的左边 ，nums[mid]肯定不是目标值了，所以得取mid - 1
因为为左闭右开，右边的right不包含，所以使得right = mid；也就相当于使得mid-1在下一次搜索范围里了。
- 完整代码如下 ：
int search(int* nums, int numsSize, int target){ int left = 0 ; int right = numsSize ; while (left < right) { int mid = left + (right - left) / 2 ; if(nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid ; } else { return mid; } } return -1; }
以上是二分查找的区间选择的最常使用的两种方式，另外还有左开右闭，思路和左闭右开也差不多。
😄新人创作不易，你的点赞和关注都是对我莫大的鼓励，再次感谢您的观看。😄
