Binary Search Application

Basic Application:

Finding target (peak, boundary, median)

1. Sorted Array(Prefix Sum array)
2. Rotated sorted array(have Peak or nadir)
3. Two sorted Array
4. BST

Advanced Application:

1. Math Calculation(power, sqrt)
2. Core of Binary Search:
   • The result set is in a certain interval
   • If current test results are not satisfied, we can shrink our result set by removing part of the results which never be the result.

Binary Search classic problems：

1. Median of Two Sorted Arrays

2. Super Pow

3. Minimum Size Subarray Sum

4. Intersection of Two Arrays II

5. Search Insert Position

6. Kth Smallest Element in a Sorted Matrix

7. Divide Two Integers

8. Wood Cut

9. Find the Duplicate Number

Basic Manipulation

Regualr Version：

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

Find First or Last Position:

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

First position: left

Last position: left == 0 ? 0 : --left

Insert position : nums[left] < target ? left + 1 : left