1. Binary Search

Template

• Basic template

// This template is to find the target from a sorted array, not consider duplicates
int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left)/2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        }
    }
    return -1;
}
// The termination condition is nums[mid] == target or left > right

• Left bound

// This template is to find the left bound
// It's used to find the target from a sorted array with the smallest index
int findLeftBound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            right = mid - 1; // Push the right pointer even when find the target
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        }
    }
    if (left >= nums.length || nums[left] != target) {
        return -1;
    }
    return left;
}

// As left < right case, the termination case is left == right
int findLeftBound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; // 注意
    
    while (left < right) { // 注意
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
}

• Right bound

// This template is to find the right bound
// It's used to find the target from a sorted array with the largest index
int findRightBound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // Push the left pointer even after finding the target
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
    if (right <= 0 || nums[right] != target) {
        return -1;
    }
    return right;
}

int findRightBound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;
    
    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left - 1; // 注意
}

// As the termination condition is left == right, it can be right - 1

总结：如果只是找到target，用left <= right, 但找左边界（最近的少于target的值），或者右边界，用left < right 更加灵活

Typical problems

• Find peak element from the array, left < right is useful for comparing index and index + 1, which is used for find local max/min

public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            // If the mid element is greater than its neighbors, it's a potential peak
            if (nums[mid] > nums[mid + 1])
                right = mid;
            else
                left = mid + 1;
        }

        // At the end of the loop, 'left' and 'right' will be equal and point to a peak element
        return left;
    }

• Search in a rotated sorted array, notice either the left half is ordered or right half is ordered, and the target either in this side or in the other side

public int searchInRotatedSortedArray(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid  = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
             // 左半段是有序的
            if (nums[left] <= nums[mid]) {
                // target 在这段里
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
                //后半段有序
            } else {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }

• Eat balance - capacity find problems

public int minEatingSpeed(int[] piles, int h) {
        int maxEatingSpeed = 0;
        for (int i = 0; i < piles.length; i++) {
          maxEatingSpeed = Math.max(maxEatingSpeed, piles[i]);
        }

        int left = 1, right = maxEatingSpeed;

        while (left < right) {
          int mid = left + (right - left) / 2;
          if (eatingHoursWithSpeed(piles, mid) > h) {
            left = mid + 1;
          } else {
            right = mid;
          }
        }
        return left;
    }

    private int eatingHoursWithSpeed(int[] piles, int itemsPerHour) {
      int hours = 0;
      for (int i = 0; i < piles.length; i++) {
        hours += piles[i] / itemsPerHour;
        if (piles[i] % itemsPerHour > 0) {
            hours++;
        }
      }
      return hours;
    }