Binary Search

Useful toturial:

• https://leetcode.com/discuss/general-discussion/786126/python-powerful-ultimate-binary-search-template-solved-many-problems

• https://www.zhihu.com/question/36132386/answer/530313852

Search in Rotated Sorted Array

Link: https://leetcode.com/problems/search-in-rotated-sorted-array/

Code:

class Solution {
    public int findRotateIndex(int[] nums) {
        int n = nums.length;
        int left = 0, right = n - 1;
        if (left == right) return 0;
        if (nums[right] >= nums[left]) return 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) return mid + 1;
            if (nums[mid - 1] > nums[mid]) return mid;
            if (nums[0] < nums[mid]) left = mid;
            if (nums[0] > nums[mid]) right = mid;
        }
        return -1;
    }
    
    public int search(int[] nums, int target) {
        int n = nums.length;
        
        // nums length is 1.
        if (n == 1) {
            if (nums[0] == target) return 0;
            if (nums[0] != target) return -1;
        }
        
        // pivot index
        int k = findRotateIndex(nums);
        
        // initialize left and right index.
        int left, right;
        if (k == 0) {
            left = 0;
            right = n - 1;
        } else if (nums[0] <= target) {
            left = 0;
            right = k - 1;
        } else {
            left = k;
            right = n - 1;
        }
        // binary search
        int mid;
        while (left <= right) {
            mid = left + (right - left) / 2; 
            if (nums[mid] == target) return mid;
            if (nums[mid] < target) left = mid + 1;
            if (nums[mid] > target) right = mid - 1;
        }
        return -1;
    }
}

First Bad Version

Link: https://leetcode.com/problems/first-bad-version/

Code:

/* 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 left = 1;
        int right = n;
        int mid;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

Sqrt(x)

Link: https://leetcode.com/problems/sqrtx/

Code:

class Solution {
    public int mySqrt(int x) {
        if (x < 2) return x;
        int left = 2;
        int right = x;
        int mid;
        while (left < right) {
            mid = left + (right - left) / 2;
            if ((long) mid * mid > x) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left - 1;
    }
}

• Special case: x = 0, x = 1;

• mid * mid may overflow, so use long.

• after exiting the while loop, left is the minimal k​ satisfying the condition

Search Insert Position

Link: https://leetcode.com/problems/search-insert-position/

Code:

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length, mid;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (target <= nums[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

Capacity To Ship Packages Within D Days

Link: https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/

Code:

class Solution {
    public int shipWithinDays(int[] weights, int D) {
        int left = 0, right = 0;
        for (int w : weights) {
            left = Math.max(left, w);
            right += w;
        }
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canShip(weights, D, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    
    private boolean canShip(int[] weights, int D, int capacity) {
        int day = 1, cur = 0;
        for (int w : weights) {
            if (cur + w > capacity) {
                day++;
                cur = 0;
            }
            cur += w;
        }
        return day <= D;
    }
}

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int left = 0;
        int right = 0;
        for (int weight : weights) {
            if (left < weight) {
                left = weight;
            }
            right += weight;
        }
        int mid;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (feasible(mid, weights, days)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    
    private boolean feasible(int capacity, int[] weights, int days) {
        int total = 0, days_used = 1;
        for (int weight : weights) {
            total += weight;
            if (total > capacity) {
                days_used += 1;
                total = weight;
            }
        }
        if (days_used > days) {
            return false;
        } else {
            return true;
        }
    }
}