拿捏二分查找
目录
一、实现原理
引理：
相信大家都玩过这样一个游戏，猜数字游戏。
游戏规则：随机写出一个1-100以内的数，让我们去猜这个数多少，每猜一次裁判员都会有提示，是否猜中，猜的数比被猜数的大小关系。
例如：写出一个56
第一次猜：猜50 提示：比被猜数小
第二次猜：猜75 提示：比被猜数大
第三次猜：猜62 提示：比被猜数大
第四次猜：猜56 提示：猜中了
以上查找的方法使用的就是二分查找，你看懂了吗？
就这！！！
二分查找的要求：待查数组是有序的
二、图解分析
举例：有这样一个数组，如图下。
我们先将Key和arr[mid]数做比较。
如果Key==arr[mid]，那么就找到了。
如果Key>arr[mid],说明查找的数可能在[mid+1,right]之间
如果Key<arr[mid],说明要查找的数可能在[left,mid-1]之间
那么从上图数组中我们来找一找Key=9
第一次查找：
mid=(left+right)/2
arr[mid]<Key
left=mid+1;
第二次查找：
mid=(left+right)/2
arr[mid]>Key
right=mid-1
第三次查找：
mid=(right+mid)/2
arr[mid]==Key
查找结束。
例子2：我想在里面查找18
第一次查找：
mid=(left+right)/2
arr[mid]<Key
left=mid+1;
第二次查找：
mid=(left+right)/2
arr[mid]<Key
left=mid+1;
第三次查找：
mid=(right+left)/2
arr[mid]<Key
left=mid+1
第四次查找：
mid=(left+right)/2
Key>arr[mid]
left=mid+1
我们可以看到left>right那么还有继续查找的必要吗？
当然没有，因为数组是有序的，没有既大于left左边的数同时又大于right右边的数，所以此数组中没有这个数。
看到这里是不是觉得很简单呀？Easy!!!
三、编程实现
//找到了返回数组下标，找不到返回-1
int BinarySearch(int *arr,int Key,int n){
int left=0;
int right=n-1;
while(left<=right){//left>right则找不到，
int mid=(right+left)/2;//中间数
if(arr[mid]==Key)
return mid;
else if(arr[mid]<Key)//条件成立查找区间改变到[mid+1,right]
left=mid+1;
else
right=mid-1;//否则查找区间改变到[left,mid-1]
}
return -1;//找不到返回-1
}
鄙人不才，勿喷，看懂的可以留个小爱心。
再见！！！！