C语言二分查找汇总 C语言基础之二分查找知识最全汇总
峡谷金城武 人气:0一、前言
在自学二分查找的过程中我想到了一些变化问题，有的自己就慢慢理解了，有的在网上找到了答案，奈何没有找到想要的总结归纳。我就斗胆自己写了一篇，号称史上最全。希望和我一样的伙伴可以少走一点弯路。
二分查找凭借其低时间复杂度O(log(n))成为了各个蒟蒻的入门知识，但是其衍生出的各种题目相较原题目而言就没有那么容易求解，以下借用c语言实现二分查找算法及其衍生。二分查找仅适用于事先已经排好序的顺序表。其基本思路就是每次取中间数，如果中间数大于所求数就向上查找，反之向下。
二、原始二分查找
1.在有序数组中寻找一个数所在下标。
int main(){
int arr[] = {1,2,3,4,5,6,7,8,9};
int left,right,fin;
fin = 3;
left = 0;right = sizeof(arr)/sizeof(arr[0])-1;
while(left <= right) {
int mid;
mid = (left+right) / 2;
if (arr[mid] == fin) {
printf("找到了：%d\n", mid);
return 0;
}
if (mid < fin)
left = mid+1;
else if (mid > fin)
right = mid-1;
}
printf("没找到");
return 0;
}
对于这种基本的排序问题，我们通过判断mid变量与key的大小对有序数组进行二分。
当查找过程中，会出现key值下标坐落在left或right上时的情况，
以下用left举例
当left = key时，一个显然的结论，此时arr[mid]无法等于key。其所作工作为减小right，进一步缩进范围，直到right = left或right = left+1，此时范围缩小到最小，mid = left。输出mid的值即为所求下标。
我们当然可以在left和right = key时直接输出key的下标，但是这样会造成多次比较。
三、二分查找的变化之数组元素重复
对于二分查找而言，会出现数组元素重复的情况，以下问题的求解建立在数组元素重复的情况下：
1.返回匹配数key的最小下标
#include <stdio.h>
int main() {
int arr[] = {1,3,3,3,3,4,5,6,7};
int left,right,lenght,key;
key = 3;
left = 0;
lenght = sizeof(arr)/sizeof(arr[0]);
right = lenght -1;
while(left <= right){
//等于的条件不能忽略
int mid = (left+right)/2;
if (arr[mid] < key)
left = mid + 1;
//目的是用left来寻找key点，不考虑mid = key的情况
else
right = mid - 1;
}
if ((left < lenght)&&(arr[left] == key))
printf("%d\n",left);
return 0;
}
当arr[mid] == key 时，此时直接输出，则无法达到最小坐标。所以我们需要移动left或right。对于移动left而言，显然移动后left将大于mid，更不可能找到最小坐标。所以需要移动right，让left逐渐逼近key的最小下标。
当arr[mid] > key时，此时需要移动right，所以此时不会出现left = key的情况
当arr[mid] < key时，此时需要移动left，前面已经知道mid<key，当left = mid + 1时，（其实类似于单调函数的求值）arr[mid] < arr[left] <=key
与原题对比，我们可以发现，只有arr[mid] == key 时产生了变化，这里有一个显然的结论，对于arr[mid] == key ，当求最小下标时，我们需要下标left<mid，所以只能移动right，当求最大下标时，我们需要right>mid，所以只能移动left。
2.返回匹配数的最大下标
#include <stdio.h>
int main() {
int arr[] = {1,3,3,3,3,4,5,6,7};
int left,right,lenght,key;
key = 3;
left = 0;
lenght = sizeof(arr)/sizeof(arr[0]);
right = lenght -1;
while(left <= right){
int mid = (left+right)/2;
if (arr[mid] <= key)
left = mid + 1;
else
right = mid - 1;
}
if ((right >= 0)&&(arr[right] == key))
printf("%d\n",right);
return 0;
}
3.返回第一个大于匹配数的下标
#include <stdio.h>
int main() {
int arr[] = {1,1,1,1,1,4,5,6,7};
int left,right,lenght,key;
key = 3;
left = 0;
lenght = sizeof(arr)/sizeof(arr[0]);
right = lenght -1;
while(left <= right){
int mid = (left+right)/2;
if (arr[mid] < key)
left = mid + 1;
else
right = mid - 1;
}
printf("%d\n",arr[left]);
return 0;
}
这个问题，比较简单，把之前的if条件注释掉就好了。=_=因为我们在循环过程中如果没有找到，left会自己停在第一个大于key的坐标上。
4.查找某个数的出现次数
这个问题就比较进阶，一开始在一篇介绍二分查找的文章里看到求出现次数，怎么想也联系不到二分查找。最后在网上找到了别人写的代码，其实就是两次二分查找，但是试了好几次也没有写对，看来我的蒟蒻路还有很长。
四、轮转循环
何为轮转（循环）有序数组，就比如说{7，8，9，0，1，2，3，4，5，6}就是一个轮转数组，其最小值不在[0]点。对于这样的数组是否可以使用二分查找，？
对于这种问题，我们需要考虑的是他的顺序起点，以{7，8，9，0，1，2，3，4，5，6}为例，他的顺序起点为a[3] = 0;
（其实把它理解成为一个分段函数最容易，但是csdn不好写数学表达式，不好画图，有兴趣的蒟蒻可以私信我）
#include <stdio.h>
int find(int arr[],int left,int right,int key) {
//传参a[]是所求数组，left,right为所求左右下标，key是所求元素
while (left <= right) {
int mid = (left + right) / 2;
if(arr[mid] > key){
if(arr[mid] < arr[right])//当此式成立时表明元素顺序起点在mid左边。
right = mid - 1;
else {//元素顺序起点在mid右边，但是key有可能在mid左边有可能在mid右边
if (key > arr[left])//在左边
right = mid - 1;
else
left = mid + 1;
}
}
else if(arr[mid] < key){
if(arr[mid] > arr[left])//在mid左边是递增的（顺序起点在[0]或右边）
left = mid + 1;
else{//顺序起点在左边且不在[0]上
if (key > arr[right])//在mid左边
right = mid - 1;
else
left = left + 1;
}
}
else//当相等时直接返回mid
return mid;
}
}
int main() {
int left,right,key,mid;
int arr[] = {7,8,9,0,1,2,3,4,5,6};
left = 0;
right =( sizeof(arr)/sizeof(arr[0]) ) - 1;
key = 4;
mid = find(arr,left,right,key);
printf("峡谷吴彦祖 %d",mid);
return 0;
}
五、杨氏矩阵
在剑指offer的项目练习上，有在杨氏矩阵中对一个数进行查找的案例。题中所给出的解题思路是利用杨氏矩阵每行递增，每列递增的性质每次排除某行或某列。而在我的实践过程中，其可以采用二分查找的思路，对大规模的矩阵进行更加优化的查找。以下是此方法的代码：
int yang_matrix_2(int arr[X][Y],int num) {
int x = 0;
int y = Y;
int a = x;
int b = y;
do{
a = x;b = y;
if (arr[x][y] > num) {//在列上进行折半查找
int left = 0;
int right = Y-1;
while (left <= right){
int mid = (((left ^ right) >> 1)+(left & right));
if (arr[x][mid] > num)
right = mid - 1;
else {
if (arr[x][mid] < num)
left = mid + 1;
else
return 1;}
}
y = left;
x--;
}
else{
if(arr[x][y] < num){
int left = 0;
int right = X-1;
while (left <= right){
int mid = (((left ^ right) >> 1)+(left & right));
if (arr[mid][y] > num)
right = mid - 1;
else {if (arr[mid][y] < num)
left = mid + 1;
else
return 1;}
}
x = right;
++y;
}//在行上进行折半查找
else
return 1;
}
}while ((x != a) && (y != b));
return 0;
}
六、用二叉树来描述二分查找
二分查找过程可用二叉树来描述：把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。
由此得到的二叉树，称为描述二分查找的判定树(Decision Tree)或比较树(Comparison Tree)。以下图为例
七、二分查找的概率问题
我们需要引入一个概念叫做平均查找长度ASL，为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度()。二分查找的ASL = log2(n+1)-1。
加载全部内容