二分通用总结

Posted on |

本篇总结下二分查找在不同的场景下的书写模板。在书写二分查找的过程中，通常会对while条件和内部判断条件有一定的困惑,这里总结一个未来通用的模板。
通用模板如下：

  • 1.第一步定义start和end。
  • 2.第二步循环中找到中间位置mid（这里需要注意数值越界）。
  • 3.第三步确定左移或者右移判断条件（具体情况具体分析）。
  • 4.第四步根据比较的结果位移（左移end=mid-1,右移start=mid+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
27
28
class Solution {
    public int binarySearch(int n) {
        //step1 定义start和end
        long start=0,end= n;

        while (start<=end){
            long mid=start+(end-start)/2;//step2 这样定义可以适当防止int越界还是不行可以用long类型
            //step3 获取比较值  这里可以视具体的情况确定
            long temp=(2+mid)*(mid+1)/2;
            //step4 根据比较的结果进行位移 注意这里必须是mid-1或者mid+1不然start的位置有可能不会超过end
            if(temp>n){
                end=mid-1;
            }else {
                start=mid+1;
            }
        }
        return start;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().arrangeCoins(8));
        System.out.println(new Solution().arrangeCoins(1804289383));
        System.out.println(new Solution().arrangeCoins(5));
        System.out.println(new Solution().arrangeCoins(1));
        System.out.println(new Solution().arrangeCoins(2));
        System.out.println(new Solution().arrangeCoins(4));
    }
}

P441. Arranging Coins

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * Example 1:
 *
 * n = 5
 *
 * The coins can form the following rows:
 * ¤
 * ¤ ¤
 * ¤ ¤
 *
 * Because the 3rd row is incomplete, we return 2.
 * Example 2:
 *
 * n = 8
 *
 * The coins can form the following rows:
 * ¤
 * ¤ ¤
 * ¤ ¤ ¤
 * ¤ ¤
 *
 * Because the 4th row is incomplete, we return 3.
 *
 */
class Solution {
    public int arrangeCoins(int n) {
        if (n==0) {
            return 0;
        }
        //step1 定义start和end
        long start=0,end= n;

        while (start<=end){
            long mid=(start+end)/2;
            //计算当前梯队的值
            long temp=(2+mid)*(mid+1)/2;
            if(temp>n){
                end=mid-1;
            }else {
                start=mid+1;
            }
        }
        return (int) start;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().arrangeCoins(8));
        System.out.println(new Solution().arrangeCoins(1804289383));
        System.out.println(new Solution().arrangeCoins(5));
        System.out.println(new Solution().arrangeCoins(1));
        System.out.println(new Solution().arrangeCoins(2));
        System.out.println(new Solution().arrangeCoins(4));
    }
}

P852. Peak Index in a Mountain Array

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 *
 * Example 1:
 *
 * Input: [0,1,0]
 * Output: 1
 * Example 2:
 *
 * Input: [0,2,1,0]
 * Output: 1
 * Note:
 *
 * 3 <= A.length <= 10000
 * 0 <= A[i] <= 10^6
 * A is a mountain, as defined above.
 *
 */
class Solution {
    public int peakIndexInMountainArray(int[] A) {
        if (A.length==0) {
            return 0;
        }
        int start=0,end=A.length-1;
        while (start<=end){
            int mid=start+(end-start)/2;

            if (A[mid+1]<A[mid]) {
                end=mid-1;
            }else {
                start=mid+1;
            }
        }
        return start;
    }

    public static void main(String[] args) {
        int[] ints={0,1,0};
        System.out.println(new Solution().peakIndexInMountainArray(ints));


        int[] ints1={0,1,2,0};
        System.out.println(new Solution().peakIndexInMountainArray(ints1));
    }
}

P162. Find Peak Element

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * 本题虽然是会出现多个peak number但是只需要定位其中一个即可
 *
 * 方法一：一遍扫描是可以的
 * 方法二：二分搜索到其中一个peak number就行
 *
 * Example 1:
 *
 * Input: nums = [1,2,3,1]
 * Output: 2
 * Explanation: 3 is a peak element and your function should return the index number 2.
 * Example 2:
 *
 * Input: nums = [1,2,1,3,5,6,4]
 * Output: 1 or 5
 * Explanation: Your function can return either index number 1 where the peak element is 2,
 *              or index number 5 where the peak element is 6.
 */
class Solution {
    public int findPeakElement(int[] nums) {
        int start=0,end=nums.length-1;
        while (start<=end){
            if (start==end && end==nums.length-1) {
                break;
            }
            int mid=start+(end-start)/2;

            if (nums[mid]<nums[mid+1]) {
                start=mid+1;
            }else {
                end=mid-1;
            }
        }
        return start;
    }

    public static void main(String[] args) {
        int[] ints={1,2,1};
        System.out.println(new Solution().findPeakElement(ints));


        int[] ints1={1,2,1,3,5,6,4};
        System.out.println(new Solution().findPeakElement(ints1));

        int[] ints2={1,2};
        System.out.println(new Solution().findPeakElement(ints2));
    }
}