正确的二分查找

     之前原来自己写的二分查找是错误的，估计大多数人写的二分查找也和我写的差不多吧，下面这链接是我之前写的错误的二分查找，现在来正确的，这个还是在july的树上看到的，感觉这个人特别厉害。

      关键的一步还是mid = left + ((right-left)>>1);因为如果我们用两个很大合理的数相加，那么就会越界啊，这里巧妙的应用的位运算。

     还有一点，尽量不要什么魔鬼数字，就是出现错误的时候很多人喜欢-1表示，你懂可是其他人不懂啊，我现在也已经慢慢养成了习惯，-1就用宏定义ERROR表示，别人也一看就懂。

 

   

#include <stdio.h>

#define ERROR (-1)

//不要尝试用魔鬼数字，比如说-1，就用宏定义ERROR代替

int half_search(int *array,int n,int value)
{
    int left = 0;
    int right = n - 1;
    int mid = 0;

    while(left <= right)
    {
        //关键是这一句话吧，这样就会保证两个合理的数相加后不会越界
        mid = left + ((right-left)>>1);

        if(array[mid] > value)
        {
            right = mid - 1;
        }
        else if( array[mid] < value)
        {
            left = mid + 1;
        }
        else
        {
            return mid;
        }
    }

    return ERROR;
}

int main(int argc,char *argv[])
{
    int array[5] = {1,5,6,9,10};
    int index = 0;

    if((index=half_search(array,5,6))== ERROR){
        printf("no find\n");
    }else{
        printf("index is %d\n",index);
    }

    return 0;
}