고성능 2분 검색 BinarySearch 반복 대체

1129 단어 StringClass
2분 찾기 코드:
package net.liuyx.algorithm;

public class BinarySearch {

    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] a = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        System.out.println(binarySearch(a, 0, a.length, -5));
    }

    private static int binarySearch(int[] a, int start, int len, int key) {
        int low = start - 1, high = start + len, guess;
        while (high - low > 1) {
            guess = (high + low) / 2;
            if (a[guess] < key)
                low = guess;
            else if (a[guess] == key)
                return guess;//          
            else
                high = guess;
        }
        //          ,     key          ,    ,     return high,     if(a[high] ==
        // key),           
        if (high == start + len || low == start - 1)// key             
            return ~high;//      ,    , ~high=-1 ,                 , ~high =
                         // -(a.length+1), ,           key        
        else
            return high;//   high  0    a.length - 1   , key              
    }
}

좋은 웹페이지 즐겨찾기