折半查找思想
基本思路：
在有序列表中，取中间元素作为比较对象，若给定值与中间元素的要查找的数相等，则查找成功；若给定值小于中间元素的要查找的数，则在中间元素的左半区继续查找；
若给定值大于中间元素的要查找的数，则在中间元素的右半区继续查找。不断重复上述查找过程，直到查找成功，或所查找的区域无数据元素，查找失败。
实现步骤：
a、low=1;high=length;//设置初始区间
b、当low>high时，返回查找失败信息//表空，查找失败
c、当low≤high,mid=(low+high)/2; //取中点
①、若key<arr[mid],high=mid-1; 转b //查找在左半区进行
②、若key>arr[mid],low=mid+1; 转b //查找在右半区进行
③、若key=arr[mid],返回数据元素在表中位置 //查找成功
注：折半查找前提：在一个有序数组中查找。
例如：key=45;
0 1 2 3 4
12 45 66 110 200
l m h
循环：mid=(l+h)/2; 如上：m=（0+4）/2;
key(值是45)<a[mid](值是66)
h=m-1;
key(值是45)>a[mid](值是12)
l=m+1;
key(值是45)=a[mid](值是45)-->查找到 |
|
收藏
淘帖
踩
