二分法
例:假设有一个容量为n+1开始的数组,从小到大存储了n个数(从下标1开始存储)。给定给定数m,求出数组中值为m的元素的下标,如果未找到则返回0。
分析: 以11个数进行分析。
首先令左边界为
left=1 ,右边界为righ@H_502_67@t=11 ,mid=(left+right)/2 即为6,判断m跟num[6]的大小。如果
num[mid]<m ,那么令left=mid+1,mid=(left+right)/2 ;如果如果nu@H_656_301@m[mid]>m ,那么令right=mid−1,mid=(left+right@H_283_403@)/2 ;如果num[mid]==m ,则返回mid。- 重复过程2,直到结束。可以得到下面这张图。
int fun(int num[],int length,int m)
{
int left = 1,right = length-1;
//因为数组是从下标0开始length比数组最后一个元素小标大1。
while(left<=right)
{
mid = (left+right)/2;
if(num[mid]<m)
{
left=mid+1;
}
else if(num[mid]>m)
{
right=mid-1;
}
else
return mid;
}
return NOT FOUND;
}
注意:
在这里是不能直接让left=mid或者right=mid的。因为可能会导致程序陷入死循环!
例:假设有一个数组num[1]=1,num[2]=2,现在要找m=3。
1.看一下令left=mid或者令right=mid的情况:
left=1,right=2,mid=1
3>num[mid],因此,left=mid=1;right=2;跟步骤1完全一致,陷入步骤1,2的死循环,出不来了。
2.再看一下令left=mid-1或者right=mid+1的情况:
left=1,因此,left=mid+1=2;right=2;mid=2
- 3>num[mid],因此,left=mid+1=3;right=2;left>right循环终止,返回NOT FOUND。