二分查找是在有序数组中查找某一个数,但是我们有时会对二分查找中循环的判断条件有疑问,或者对循环中的if语句有疑问。
其实二分查找本质上是一种区间查找,你的区间就取决于你的left和right的值。我们先给出一个我们习以为常的二分查找:
//nums[] = 1,2,3,4,5,6,7,8,9,10
//k从1~10
bool BinarySearch(int *nums, int numsSize, int k)
{
int left = 0;
int right = numsSize - 1;
int mid = 0;
while (left <= right)
{
mid = left + (right - left) / 2;
if (k > nums[mid])
{
left = mid + 1;
}
else if (k < nums[mid])
{
right = mid - 1;
}
else
{
return true;
}
}
return false;
}
我们给出的left是0,右端点是right = numsSize -1的时候,即右端点就是数组的最后一个数据,这就表明我们这次的二分查找是闭区间——[left,right],那么当我们的left和right重叠的时候,还有一个数据会被查询到。而且,不管k大于还是小于nums[mid],此时因为是闭区间,所以我们可以直接让left = mid +1或者right = mid -1。
那当我们的right不再是 numsSize-1的时候,而是numsSize的时候,此时我们的区间就不再是[left,right]这样的闭区间了,因为nums的下标是0~numsSize-1,所以此时的区间应该为——[left,right)这样的左闭右开区间。
此时,while循环的判断条件就应该改成小于了。因为这样是为了避免数组越界。
那这样就可以了么?
当然不行!
如果当k大于nums[mid]的时候,因为是左闭区间,mid已经查找过了,所以left应该等于mid+1;
当k小于nums[mid]的时候,因为右边是开区间,虽然mid已经查找过了,但是right可以等于mid-1么?如果right = mid -1,而右边又是开区间,那么不就等于这个区间少了一个数么?所以,此时的right应该等于mid。
//nums[] = 1,2,3,4,5,6,7,8,9,10
//k从1~10
bool BinarySearch(int *nums, int numsSize, int k)
{
int left = 0;
int right = numsSize;
int mid = 0;
while (left < right)
{
mid = left + (right - left) / 2;
if (k > nums[mid])
{
left = mid + 1;
}
else if (k < nums[mid])
{
right = mid;
}
else
{
return true;
}
}
return false;
}
综上所述,二分查找中while循环的条件判断语句以及if语句中的小细节主要在于我们的区间是闭区间还是左闭右开区间。如果是闭区间,那么while循环就是小于等于,如果是左闭右开区间,那么while循环就是小于。区间主要取决于right的值是numsSize-1,还是numsSize。