C语言实现简单二分搜索和四个变体问题

本文主要是介绍C语言实现简单二分搜索和四个变体问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二分查找

简单的二分查找

简单指的是在不存在重复元素的数组中，查找值等于给定值的情况。

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;
}

二分查找的局限性