查找-二分查找

2.1 思路：二分查找前提是查找的數組是有序的，利用數據有序的特性提高查找性能。首先與數組中間位置的值比較，如果查找值大於中間位置值，則對數組右邊以相同的思路查找，否則在左邊以相同方式查找。這種方式使得每次查找範圍變為原來的1/2.
2.2 時間複雜度: O(log2n)

2.3 空間複雜度: O(1)

<code>public int halfSearch(int[] array, int num) {
    if(array == null || array.length == 0) {
         return -1;
    }
    int lo = 0, hi = array.length-1;
    while(lo <= hi) {
        int mid = (lo + hi) >> 1;
        if (array[mid] == num) {
            return mid;
        } else if (array[mid] < num) {
            hi = mid -1;
        } else {
            lo = mid + 1;
        }
    }
    return -1;
}/<code>

2.4 變種二分查找

http://www.cr173.com/html/20428_1.html

閱讀更多 醉人Ryu 的文章

關鍵字: 複雜度 二分 查找