0%

Binary Search.

Posted on Edited on Valine:

BS Mind

排除法找二分

边界收缩问题

限制条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int binarySearch(int[] array, int des) {
     int low = 0, high = array.length - 1;
     while (low <= high) {
         int mid = low + (high - low) / 2;//int mid = (left + right) >> 1;
         if (des == array[mid]) {
             return mid;
         } else if (des < array[mid]) {
             high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {

    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        // 注意：针对特殊测试用例，例如 2147395599
        // 要把搜索的范围设置成长整型
        long left = 1;
        long right = x / 2;
        while (left < right) {
            // 注意：这里一定取右中位数，如果取左中位数，代码会进入死循环
            // long mid = left + (right - left + 1) / 2;
            long mid = (left + right + 1) >>> 1;
            long square = mid * mid;
            if (square > x) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        // 因为一定存在，因此无需后处理
        return (int) left;
    }

}

二分查找

Binary Search Solution in Leetcode

二分查找细节详解_labuladong