【算法思想04】二分查找

即使用二分查找在区间[0,x]中查找x的平方根

class Solution {
    public int mySqrt(int x) {
        if (x <= 1) return x;

        int l = 1, h = x;
        while (l <= h) {
            int m = l + (h-l) / 2;
            if (x/m == m) {	// 使用m*m会溢出
                return m;
            } else if (x/m < m) {   // target in [l, m-1]
                h = m - 1;
            } else {    // target in [m+1, h]
                l = m + 1;
            }
        }
        return h;   // 退出循环的条件是l>h，所以此时h总是小于l的，因此返回h而不是返回l
    }
}

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int l = 0, h = letters.length - 1;
        while (l <= h) {
            if (letters[l] > target) return letters[l];

            int m = l + (h-l) / 2;
            if (letters[m] <= target) {	// target in [m+1, h]
                l = m + 1;
            } else {	// target in [l, m]
                h = m;
            }
        }
        return letters[0];
    }
}

令target为单一元素在数组中的位置
在target之后，数组中原来存在的成对状态被改变

如果m为偶数
当m + 1 < index，有nums[m] == nums[m+1]
当m + 1 >= index，有nums[m] != nums[m+1]

class Solution {
    public int singleNonDuplicate(int[] nums) {
    	int l = 0,h = nums.length - 1;
    	while (l < h) {
    		// 保证l、m、h都在偶数位，使得查找区间的长度为奇数
            if (m % 2 == 1) m--;
            
            if (nums[m] == nums[m+1]) { // target in [m+2, h]
                l = m + 2;
            } else {    // target in [l, m]
                h = m;
            }
    	}
    	// l=h，不返回nums[m]
        return nums[l];
	}
}

使用二分查找，找到[false,false,...,false,true,true,...true]中第一个true的下标

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int l = 1, h = n;
        while (l <= h) {
            int m = l + (h-l) / 2;
            if (isBadVersion(m)) {  // target in [l, m-1]
                h = m - 1;
            } else {    // target in [m+1, h]
                l = m + 1;
            }
        }
        return l;
    }
}

class Solution {
    public int findMin(int[] nums) {
        int l = 0, h = nums.length-1, m=0;
        while (l < h) {
            m = l + (h-l) / 2;
            if (nums[m] > nums[h]) {   // target in [m+1, h]
                l = m + 1;
            } else {    // target in [l, m]
                h = m;
            }
        }

        return nums[l];
    }
}

使用二分查找的方式缩小区间，查找数组nums中元素的值都为target的子区间[l, h]

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int l = 0, h = nums.length - 1;

        while (l <= h) {
            int m = l + (h-l) / 2;

            if (nums[m] < target) { // target in [m+1,h]
                l = m + 1;
            } else if (nums[m] > target) {  // target in [l,m-1]
                h = m - 1;
            } else {    // nums[m] == target
                if (nums[l] == nums[h]) {
                    if (nums[l] == target) return new int[]{l,h};
                    else return new int[]{-1,-1};
                }
                if (nums[l] < target) l++;
                if (nums[h] > target) h--;
            }
        }
        return new int[]{-1,-1};
    }
}

对于所有有效的 i 都有 nums[i] != nums[i + 1]
.
由提示知相邻元素的值不相等，寻找数组中的极大值（该值也可能是边界值）
input: [1,2,3] - > output: 2

class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0, h = nums.length - 1;
        while (l < h) {
            int m = l + (h-l) / 2;
            if (nums[m] < nums[m+1]) {  // target in [m+1, h]
                l = m + 1;
            } else {   // target in [l, m]
                h = m;
            }
        }
        return l;
    }
}

枚举时间 t 能都修完所有汽车。假设最少时间为 t，则
时间大于等于 t 都可以修完，否则都修不完，所以 t 的值域具有单调性，可以枚举 t 并使用二分查找。
.
在ranks[i]*n^2的时间内可以修完n辆车 -> 机械工i的效率为1/ranks[i]
随机取一个机械工修完所有车的时间作为上界

class Solution {
    public long repairCars(int[] ranks, int cars) {
        long left = 0, right = 1l * ranks[0]*cars*cars; // 防止溢出
        long mid = 0;

        while (left < right) {
            mid = left + (right - left) / 2;
            
            if (check(ranks, cars, mid)) {  // 判断mid分钟内机械工们能否修完cars
                right = mid;    // 能修完。移动上界
            } else {
                left = mid + 1; // 修不完。移动下界
            }
        }

        return left;    // 一定是执行left=mid+1后才跳出循环的
    }

    private boolean check(int[] ranks, int cars, long mid) {
        long cnt = 0;
        for (int x : ranks) {   // 累计每个机械工在mid分钟内修完的汽车数目
            cnt += (long) Math.sqrt(mid / x);
        }

        return cnt >= cars;
    }
}