博客

二分查找的基本思想：在有序表中，取中间数作为比较对象，若给定值与中间值相等，则查找成功；若中间值大于给定值，则在中间值左侧区域查找；若中间值小于给定值，则在中间值右侧区域查找，不断重复上述过程，知道找到为止；

由上面的叙述可知，使用二分查找需要满足两个前提条件：

（一）待查找的列表必须有序

（二）必须使用线性表的顺序存储数据结构

int birarySearch(int *array, int key, int length) {

    int low = 0;
    int high = length - 1;

    while (low <= high) {
        int mid = (low + high)/2;
        if (array[mid] == key) { // 判断中间值是否与给的值相等，相等就直接返回
            return mid;
        } else {
            if (array[mid] < key) { 
                low = mid + 1; // 扩大下限
            } else {
                high = mid - 1; // 缩小上限
            }
        }
    }

    return -1; // 没有找到
}

参考：

http://www.cnblogs.com/mcgrady/archive/2013/08/19/3268923.html



http://zhidao.baidu.com/link?url=f40wKtz-SPKBSGOiw2L4B7PglJJVZJg14QjHsSm_9Ryga9X7kqFINN9kUQfvSo_6IOSF1aDwKJy2JFr9idRd4J1R1ppY4x0nGx-pM_ey16K



http://sjjp.tjuci.edu.cn/sjjg/DataStructure/DS/web/xianxingbiao/xianxingbiao2.1.1.htm