二分法

例：假设有一个容量为n+1开始的数组，从小到大存储了n个数(从下标1开始存储)。给定给定数m,求出数组中值为m的元素的下标，如果未找到则返回0。

分析： 以11个数进行分析。

  1. 首先令左边界为 <nobr> left=1 </nobr>，右边界为 <nobr> right=11 </nobr>， <nobr> mid=(left+right)/2 </nobr> 即为6，判断m跟num[6]的大小。

  2. 如果 <nobr> num[mid]<m </nobr>,那么令 <nobr> left=mid+1,mid=(left+right)/2 </nobr>;如果如果 <nobr> num[mid]>m </nobr>,那么令 <nobr> right=mid−1,mid=(left+right)/2 </nobr>;如果 <nobr> num[mid]==m </nobr>,则返回mid。

  3. 重复过程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的情况：

  1. left=1,right=2,mid=1

  2. 3>num[mid],因此，left=mid=1;right=2;跟步骤1完全一致，陷入步骤1,2的死循环，出不来了。

2.再看一下令left=mid-1或者right=mid+1的情况：

  1. left=1,right=2,mid=1

  2. 3>num[mid],因此，left=mid+1=2;right=2;mid=2

  3. 3>num[mid],因此，left=mid+1=3;right=2;left>right循环终止，返回NOT FOUND。