彻底搞懂二分查找区间

大家好，欢迎来到IT知识分享网。

一、文章概述

        相信大家对二分查找都不陌生，但是很多人都搞不明白二分查找的区间是left<=rigth，还是left<rigth。上面两种情况是我们经常遇到的，下面就帮助读者明白这两种情况的区别。由于自己学识浅薄，难免有错误和不足之处，恳请大家的指正。

二、区分二分查找区间

        首先这两种情况都是正确的，但是对应不同的情况在代码实现时有细微的差别。

（一）left <= rigth的情况（左闭右闭）

这种情况下，我们初始时我们要让left = 0、right = 9；要查找元素为target = 6

       由图可知，初始状态时left指向的1和right指向的10都是在查找区间内的，在下面的查找区间中我们也要保持这一条件，即left和right指向的元素都在查找区间内，比如在图中第二次查找时，目标元素5>arr[mid],此时我们已经可以确定我们要查找的元素不是arr[mid],所以在下次的查找区间 ，我们不应该包含arr[mid],从而让left = mid+1，而不是left = mid。

代码可以写成如下形式：

#include<stdio.h> int main() { int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int left = 0, right = 9, target = 6; while (left <= right) { int mid = (right + left)/2; if (target > arr[mid]) {//当target > arr[mid]时，可以确定要找的元素不是arr[mid] left = mid + 1;//我们又要保证，left位置的元素包含在查找区间中，所以让left = mid+1 } else if (target < arr[mid]) {//当target < arr[mid]时，可以确定要找的元素不是arr[mid] right = mid - 1; //我们又要保证，right位置的元素包含在查找区间中， //所以让right = mid - 1; } else { printf("找到了！"); break; } } if (left > right) { printf("未找到！"); } return 0; }

（二）left < right的情况（左闭右开）

这种情况下，初始时我们要让left = 0、right = 10,要查找元素为target = 2

        初始时left = 0、 right = 10的情况，我们可以将查找区间理解为[left,right);也就是right所指向的元素是不被包含在查找区间中的，而left指向的元素包含在查找区间中。例如上图中，第一次的查找的区间left = 0、right = 10，left指向的元素1包含在查找区间中，而right指向的未知元素不被包含在查找区间中；在设置第二次的查找区间时我们也要确保与第一次的条件相同，所以第二次的查找区间为left=1,right = mid,因为我们已经确定target<mid（2<6）,我们又要保证right位置的元素不包含在查找区间中，所以让right = mid；

代码形式如下：

#include<stdio.h> int main() { int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int left = 0, right = 10, target = 2; while (left < right) { int mid = (right + left)/2; if (target > arr[mid]) {//target > arr[mid]时，可以知道要找的元素不是arr[mid] left = mid+1;//我们要保证left位置的元素，包含在查找区间中，所以left = mid+1 } else if (target < arr[mid]) {//target < arr[mid]时，可以知道要找的元素不是arr[mid] right = mid;//我们要保证right位置的元素，不包含在查找区间中，所以right = mid； } else { printf("找到了！"); break; } } if (left >= right) { printf("未找到！"); } return 0; }

三、总结

        以上两种情况的共同点便是，我们要始终保持查找区间的条件不变，第一种情况中，left和right位置的元素都在查找区间中，那么在整个过程中我们都要保证left和right位置的元素在查找区间中；第二种情况中，left位置的元素在查找区间中，right位置的元素不在查找区间中，那么我就要始终保持left位置的元素在查找区间中，right位置的元素不在查找区间中。