二分查找是很基础的一种算法
例题：
在一个有序数组中查找具体的某个数，如果找到了返回，这个数的下标。找不到的返回-1
其原理图如图所示
因为是有序的数列，所以可以将要查找的数与中间的数进行比较，如果要查找的数比中间的数大，那么他就在中间数的右边，反之，就在中间数的左边
例如上图，设上图序列为数组a
中间的数为a[0]+a[9]/2，即5
如果要查找的数比5大，那么缩小范围，对5右边的数在进行二分，此时的范围是
a[6]~a[9]之间，右边的数（a[9]）不变，左边的数变为a[5+1]
如果要查找的数比5小，那么就缩小范围，对5左边的数进行二分，此时的范围是a[0]~a[4]
左边的数a[0]不变，右边的数变为a[5-1],将这个思路广泛化，得到关键代码如下：
//根据索引确定中间的数，在让中间的数arr[mid],与left或者right进行比较 //left，right，mid计算的都是下标,因为返回的值需要为下标 //而进行比较的值是arr[mid]，即中间下标对应的值 int binary_search(int arr[],int k,int sz)//sz表示这个数组的长度 { int left,right; left=0; right=sz-1;//最右边的数的下标是数组长度-1，例如数组长度是10，那么最右边数的下标就是a[9] while(left<=right)//如果left大于right，表示找不到该数 { int mid=(left+right)/2;//中间的数的下标 if(k<arr[mid]) right=mid-1; else if(k>arr[mid]) left=mid+1; else return mid; } return -1; }
那么最终代码如下：
#include<stdio.h> int binary_search(int arr[],int k,int sz) { int left,right; left=0; right=sz-1; while(left<=right) { int mid=(left+right)/2; if(k<arr[mid]) right=mid-1; else if(k>arr[mid]) left=mid+1; else return mid; } return -1; } int main() { int arr[]={1,2,3,4,5,6,7,8,9,10}; int k=7; int sz=sizeof(arr)/sizeof(arr[0]); int ret=binary_search(arr,k,sz); if(ret==-1) printf("找不到指定的数字\n"); else printf("%d",ret); return 0; }
注意事项：非常关键
1.mid不能写在while循环的外面
int binary_search(int arr[],int k,int sz) { int left,right; left=0; right=sz-1; int mid=(left+right)/2; while(left<=right) { if(k<arr[mid]) right=mid-1; else if(k>arr[mid]) left=mid+1; else return mid; } return -1; }
因为mid的值会根据left和right值的改变而改变了，如果mid值不变，就不能进行范围的缩小，只能进行一次二分查找，得不到最终结果
2.left<=right不能少了=
int binary_search(int arr[],int k,int sz) { int left,right; left=0; right=sz-1; while(left<right) { int mid=(left+right)/2; if(k<arr[mid]) right=mid-1; else if(k>arr[mid]) left=mid+1; else return mid; } return -1; }
如果left和right同时指向这一元素，而这一元素正好是我们需要查找的元素，写为left<right的话,那么就会跳过我们需要查找的元素，返回-1
3.binary_search函数不能写为如下形式
int binary_search(int arr[],int k) { int left,right; left=0; sz=sizeof(arr)/sizeof(arr[0]); right=sz-1; while(left<=right) { int mid=(left+right)/2; if(k<arr[mid]) right=mid-1; else if(k>arr[mid]) left=mid+1; else return mid; } return -1; }
即，在该函数内计算数组的大小
因为数组在传参的时候，只会传递数组的第一个元素的地址，int arr[]是指针类型的参数，即int *arr,所以对于sizeof(arr)是一个地址的大小，即4，而arr[0]是int类型元素，其大小也为4
所以这里的sz=1/1=1，得不到最终的结果，这一点千万注意。
