1.4.1 折半查找_自己动手写分布式搜索引擎-QQ阅读男生科幻网

上QQ阅读APP看书，第一时间看更新

1.4.1 折半查找

为了快速地查找单词，可以先对单词列表排序，例如：《新华字典》和《现代汉语词典》按拼音排序。从排好序的词表中查找一个词，可以采用折半查找的方法快速查询。下面是实现折半查找的代码。

        int binarySearch(String[] a, String key){
            int low = 0; //开始位置
            int high = a.length -1; //结束位置


            while (low <= high) {
                int mid = (low + high) >>> 1; //相当于mid = (low + high)/2
                String midVal = a[mid]; //取中间的值
                int cmp = midVal.compareTo(key); //中间值和要找的关键词比较


                if (cmp < 0)
                    low = mid + 1;
                else if (cmp > 0)
                    high = mid -1;
                else
                    return mid; // 查找成功，返回找到的位置
            }
            return -(low + 1);  // 没找到，返回负值
        }