二分法查找有序数组里的元素

设数组arr有n个元素，且从小到大有序排列，要查找的数num一定在数组中，把数组看作一个区间段，并且设区间段左端的元素为arr[left],右端的元素为arr[right]，设middle=（left+right）/2。

当n为奇数时，把数组分成前，后两段，且arr[middle]在前半段，前半段元素个数比后半段个数多1。

当n为偶数时，把数组分成前，后两段，且arr[middle]在前半段，前，后两段元素个数相等。

因为要查找的值一定在数组中，所以要查找的元素要么在前半段，要么在后半段，故比较num与arr[middle]的值。

若num<arr[middle],则说明num在前半段，即在arr[left]至arr[middle-1]中。 若num>arr[middle],则说明num在后半段，即在arr[middle+1]至arr[right]中。 若num==arr[middle],则说明直接找到。

若没有找到，当num<arr[middle]时，即num在区间段arr[left]至arr[middle-1]中，则继续划分，重复以上的步骤，即区间段左端元素仍为arr[left],右端元素变为arr[left]=arr[middle-1];同理，当num>arr[middle]时，区间段左端元素变为arr[left]=arr[middle+1],右端元素仍为arr[right]。

以上步骤一直重复，如果一直都没找到所要查找的元素，则逐渐地，区间段的长度就会原来越短，会出现这样的情况：

……

区间段含4个元素：

区间段含3个元素：

区间段含2个元素：

区间段含1个元素：

当区间段含一个元素:此时这个元素必然就是要找的数num，此时有arr[left]==arr[right]==num，即有left==right。

当区间段含两个元素：则此时继续将区间段一分为二，前半段与后半段都只含一个元素，此时要么查找的数就是前半段那个唯一的元素，要么查找的数就是后半段那个唯一的元素。当查找的元素在前半段时，此时有arr[middle]==arr[(left+right)/2]==arr[left]==num<arr[right],即有left<right；当要查找的元素在后半段时,此时arr[left]=arr[middle+1]，即有arr[left]==arr[right]==num,即有left==right；

当区间段含三个元素时：继续划分一下，要么直接找到num==arr[middle],要么区间段减小变为含一个元素的情况。

当区间段含四个元素时，继续划分一下，要么直接找到num==arr[middle],要么区间段减小变为含一个元素或含两个元素时的情况。

……

综上，会发现要查找num时，无论数组元素个数n为奇数或者n为偶数对结果都没有影响。并且我们还会发现，当查找到要找的数num时，都一定有left<=right； 特别地，如果要查找的数num不在数组中，则最后区间段的长度必定会变为1，此时有arr[left]==arr[right]!=num,即有left==right。

以下是代码实现

int left=0；
int middle=0；
int right=sizeof（arr）/arr[0]-1;
while(left<=right)
{
    middle=(left+right)/2;
    if(num<arr[middle])
    {
         left=left; //其实这一行是多余的，加上来可以方便我们理解查找过程
         right=middle-1;
    }
    else if(num>arr[middle])
    {
        left=middle+1;
        right=right; //同样是多余的一行
    }
    else
    {
         //若找到要查找的数，则直接跳出循环，该数下标就为middle，
         //即有arr[middle]==num,若找不到，则最后arr[middle]!=num。
         break；
    }
}

以上数组元素从小到大排列的查找方式，若排序方式为从大到小，只需把上述if—else语句的判断条件改成相反的即可。