sortarrayhalffind.java

来自「6个经典数据结构JAVA解法」· Java 代码 · 共 46 行

/**
 * 二分查找的find()方法：(用于有序数组，相对于无序数组线性查询快的多)
 * 规则：找中值，比较中值与查询数字，如果中值大，去小的那一半，
 * 然后再取中值对比，直到找到为止，找不到返回数组长度.
*/
public class SortArrayHalfFind{
    
    /**
     * 二分法查询实现  
     * @param long searchKey
     * @return int result(the order in array)
     */
    public static int find(long searchKey,int[] array) {
        int nElems = array.length;
        int lowerBound = 0;
        int upperBound = nElems - 1;
        int curIn;
        System.out.println("nElems=="+nElems);
        while (true) {
            curIn = (lowerBound + upperBound) / 2;
            System.out.println("curIn=="+curIn);
            if (array[curIn] == searchKey) {
                return curIn; // found it
            } else if (lowerBound > upperBound) {
                return nElems; // can't find it
            } else { // divide range
                if (array[curIn] < searchKey) {
                    lowerBound = curIn + 1; // it's in upper half
                 } else {
                    upperBound = curIn - 1; // it's in lower half
                }
            } // end else divide range
        } // end while
    } // end find()
    
    /**
     * 主函数，测试。
     * @param String[] args
     */
    public static void main(String[] args) {
        int[]test = {1,20,50,55,56,70,100,100}; 
        int result = SortArrayHalfFind.find(50,test);  
        System.out.println("the order in test array is "+ result); 
    }
     
}