/* 二分查找 * 算法思想：1、将数组排序(从小到大)；2、每次跟中间的数mid比较，如果相等可以直接返回， * 如果比mid大则继续查找大的一边，否则继续查找小的一边。  输入：排序好的数组 - sSource[]，数组大小 - array_size，查找的值 - key  返回：找到返回相应的位置，否则返回-1*/int BinSearch(int sSource[], int array_size, int key){        int low = 0, high = array_size - 1, mid;        while (low <= high)    {                mid = (low + high) / 2;//获取中间的位置                if (sSource[mid] == key)                        return mid;    //找到则返回相应的位置        if (sSource[mid] > key)                        high = mid - 1;    //如果比key大，则往低的位置查找        else            low = mid + 1;    //如果比key小，则往高的位置查找    }        return -1;    }

/* * 编写一个函数，对一个已排序的整数表执行二分查找。 * 函数的输入包括各异指向表头的指针，表中的元素个数，以及待查找的数值。 * 函数的输出时一个指向满足查找要求的元素的指针，当未查找到要求的数值时，输出一个NULL指针 * 用两个版本实现，一个用的是数组小标，第二个用的是指针 * 他们均采用了不对称边界 * Copyright (c) 2012 LiMingAuthor:        LiMing2012-06-21referenced C Traps and Pitfaills Chinese EditionPage 132-137 *  * 查找的元素为x，数组下表是k，开始时0 <= k < n * 接下来缩小范围lo <= k < hi, * if lo equals hi, we can justify the element "x" is not in the array  * */#include <stdio.h>int array[] = {        0,1,2,3,4,5,6,7};int *bsearch_01(int *t, int n, int x);int *bsearch_01(int *t, int n, int x){    int lo = 0;    int hi = n;        while(lo < hi)    {        //int mid = (hi + lo) / 2;        int mid = (hi + lo) >> 1;                if(x < t[mid])            hi = mid;        else if(x > t[mid])            lo = mid + 1;        else            return t + mid;            }    return NULL;}int *bsearch_02(int *t, int n, int x);int *bsearch_02(int *t, int n, int x){    int lo = 0;    int hi = n;        while(lo < hi)    {        //int mid = (hi + lo) / 2;        int mid = (hi + lo) >> 1;        int *p = t + mid;        //用指针变量p存储t+mid的值，这样就不需要每次都重新计算                if(x < *p)            hi = mid;        else if(x > *p)            lo = mid + 1;        else            return p;            }    return NULL;}//进一步减少寻址运算/* * Suppose we want to reduce address arithmetic still further  * by using pointers instead of subscripts throughout the program. *  * */int *bsearch_03(int *t, int n, int x);int *bsearch_03(int *t, int n, int x){    int *lo = t;    int *hi = t + n;        while(lo < hi)    {        //int mid = (hi + lo) / 2;        int *mid = lo + ((hi - lo) >> 1);                if(x < *mid)            hi = mid;        else if(x > *mid)            lo = mid + 1;        else            return mid;        }    return NULL;}/* * The resulting program looks somewhat neater because of the symmetry * */int *bsearch_04(int *t, int n, int x);int *bsearch_04(int *t, int n, int x){    int lo = 0;    int hi = n - 1;        while(lo <= hi)    {        //int mid = (hi + lo) / 2;        int mid = (hi + lo) >> 1;                if(x < t[mid])            hi = mid - 1;        else if(x > t[mid])            lo = mid + 1;        else            return t + mid;        }    return NULL;}int main(int argc, char **argv){    int * ret = NULL;    int *ret2 = NULL;    int *ret3 = NULL;    int *ret4 = NULL;        ret = bsearch_01(array, 8, 3);    ret2 = bsearch_02(array, 8, 6);    ret3 = bsearch_03(array, 8, 4);    ret4 = bsearch_04(array, 8, 2);    printf("The result is %d\n", *ret);    printf("The result is %d\n", *ret2);    printf("The result is %d\n", *ret3);    printf("The result is %d\n", *ret4);        printf("hello world\n");    return 0;}

int BinSearch(int Array[],int low,int high,int key/*要找的值*/){    if (low<=high)    {        int mid = (low+high)/2;        if(key == Array[mid])            return mid;        else if(key<Array[mid])            return BinSearch(Array,low,mid-1,key);        else if(key>Array[mid])            return BinSearch(Array,mid+1,high,key);    }    else        return -1;}

int BinSearch(int Array[],int SizeOfArray,int key/*要找的值*/){    int low=0,high=SizeOfArray-1;    int mid;    while (low<=high)    {        mid = (low+high)/2;        if(key==Array[mid])            return mid;        if(key<Array[mid])            high=mid-1;        if(key>Array[mid])            low=mid+1;    }    return -1;}