二分查找
简单的二分查找
简单指的是在不存在重复元素的数组中，查找值等于给定值的情况。
int bsearch(int *arr, int n, int value)
{
int low = 0;
int high = n - 1;
int mid;
while (low <= high){
mid = low + ((high-low) >> 1);
if (arr[mid] == value){
return mid;
} else if(arr[mid] < value){
low = mid + 1;
} else{
high = high - 1;
}
}
return -1;
}
二分查找容易出错的三个地方
- 循环退出 条件，low<=high
- mid取值，需要考虑到溢出，改写为low+(high-low)/2比较好
- low和high的更新。不能直接写成low=mid, high=mid, 否则可能了；出现死循环
二分查找的变体
在实际数据中，我们要查找的值可能在数据集中并不存在，或者有有多个，那么上面的代码就不在适用了。常见的4个问题
- 查找第一个值等于给定值的元素
- 查找最后一个值等于给定值的元素
- 查找第一个大于等于给定值的元素
- 查找最后一个小于等给定值的元素
寻找第一个值等于给定的元素的关键在于，当发现arr[mid]== value时，我们不确定mid是不是第一个等于value的位置。
当mid是位于数组的开头，或者该位置的前一个并不等于value时，我们就可以保证mid就是第一个，否则的话，就意味着第一个值出现在mid前面。
int bSearchFirstEqual(int *arr, int n, int value)
{
int low = 0;
int high = n-1;
int mid;
while (low <= high){
mid = low + ( (high-low) >> 1);
// 如果中间的数字比给的值大
// 数据应该在low-mid里
if (arr[mid] > value){
high = mid - 1;
// 如果中间的数字比给的值小
// 数据应该在mid-high里
} else if( arr[mid] < value){
low = mid + 1;
} else{
//如果相等, 先看这个位置是不是第一个, 或者它的前面值是否和它相等
//如果mid是第一个或者是前面值不等, 当前值就是所找的值
if ( mid == 0 || arr[mid-1] != value) return mid;
//否则应该在mid-high中
else high = mid - 1;
}
}
return -1;
}
寻找最后一个值等于给定的元素和上面类似于，只不过当发现arr[mid]== value时，我们不确定mid是不是最后一个等于value的位置。
当mid是位于数组的末尾，或者该位置的后一个并不等于value时，我们就可以保证mid就是最后一个，否则的话，就意味着第一个值出现在mid后面。
int bSearchLastEqual(int *arr, int n, int value)
{
int low = 0;
int high = n - 1;
int mid ;
while ( low <= high){
mid = low + ( (high-low) >> 1);
if (arr[mid] > value ){
high = mid - 1;
} else if ( arr[mid] < value){
low = mid + 1 ;
} else {
if ( mid == n -1 || arr[mid+1] != value) return mid;
else low = mid + 1;
}
}
return -1;
}
寻找第一个大于等于某个值的位置，只考虑大于等于和小于等于两种情况。如果arr[mid]小于给定的值，就说明我们应该在mid后面查找。而当我们发现arr[mid] >= vlaue, 我们就要分析下这个是不是第一个大于给定值的地址。显然如果mid是第一个或者a[mid-1] < value就说明mid就是我们要找的，否则的话，就说明目前位置靠后了，我们需要把上限移动到mid
int bSearchFirstLarge(int *arr, int n, int value)
{
int low = 0;
int high = n -1;
int mid;
while (low <= high){
mid = low + ((high-low) >> 1);
if (arr[mid] >= value){
if ( mid == 0 || arr[mid-1] < value ) return mid;
else high = mid - 1;
} else{
low = mid + 1;
}
}
return -1;
}
查找最后一个小于等给定值的元素, 也是分为小于等于和大于两种情况。当arr[mid] <= value时，也是考虑mid是不是最后一个位置，或者说mid的后一个位置已经比当前值大。否则就说明目标位置比mid小。
int bSearchLastLess(int *arr, int n, int value)
{
int low = 0;
int high = n -1;
int mid;
while (low <= high){
mid = low + ((high-low) >> 1);
if (arr[mid] > value){
high = mid - 1;
} else{
if ( mid == n-1 || arr[mid+1] > value) return mid;
else low = mid + 1;
}
}
return -1;
}
二分查找的局限性
- 二分查找只能用于数组这类支持随机访问的顺序表
- 二分查找只能用在有序数据
- 对于小数据，没必要二分查找，直接遍历即可
- 二分查找需要连续的内存，因此对于过大的数据集，就无法加载到数组中。
