Binary Search (Part 1)

35	Search Insert Position

(1) return lower_bound(nums.begin(), nums.end(), target) - nums.begin();

(2) Implement 3 part BS (binary search):

    while (l <= r)

          if (nums[mid] == target)

              return mid;

          else if (nums[mid] < target)

              l = mid + 1;

          else

              r = mid - 1

    return l;

Both are O(lgN) time and O(1) space.

162	Find Peak Element

  while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] > nums[mid + 1])
                r = mid;
            else
                l = mid + 1;
        }
      
        return l;

167	Two Sum II - Input array is sorted

(1) Use hash map to save the elements encountered so far. And check whether target - current_num_val is already in the hash map, if so push both of their indices into the result array and return them.

(2) Two pointers, left pointer and right pointer. Let sum = numbers[left] + numbers[right], if sum == target, return {left + 1, right + 1}. Else if sum > target, right--, Else left++. If not early return  after the loop, return {0, 0} meaning not exist. O(N) time and (1) space.

(3) lg(N) time and O(1) space improved on (2). Instead of moving 1 by 1 from left or right. We could do binary search when sum is not equal target. If sum < target, we could left left = findNextGreaterOrEqual(numbers, left, right, target - numbers[right]); Else if sum > target, we could let right = findNextSmallOrEqual(numbers, left, right, target - numbers[left]); For findNextGreaterOrEqual and findNextSmallOrEqual,  it is just ordinary 3-part left <= right binary search.  Only difference is the former return left, and the later return right.

367	Valid Perfect Square

typical O(lg(n)) binary Search algorithm, O(1) space

374	Guess Number Higher or Lower

typical O(lg(n)) binary Search algorithm, O(1) space

441	Arranging Coins

(Solution 2, binary search O(lgN))
Since we know (x^2+x) / 2 = n, we iterate in binary search to use (x^2+x) / 2 to approach n.
i.e:  mid = low + (high - low ) /2
if ((0.5 * mid * mid + 0.5 * mid) <= n)
         low = mid + 1;
else
         high = mid - 1
 return (low - 1)

74	Search a 2D Matrix

left = 0, right = m * n -1, while left <= right, if matrix[i][j] == target return true, else if target >  matrix[i][j]    right = mid - 1, else left = mid + 1 (where i = mid / n, j = mid % n). Return false in the end. O(lg(M*N)) time and O(1) space

You can also do saddle search from top right, i.e: row = 0, col = n - 1, if matrix[row][col] == target return true, if target > matrix[row][col] col--, else if target < matrix[row][col] row++, return false in the end. But O(M + N) time and O(1) space.

69

Sqrt(x)

Same with 441. Arranging Coins, binary search. Except use if (mid <= n / mid) to replace if ((0.5 * mid * mid + 0.5 * mid) <= n)

278	First Bad Version

  int firstBadVersion(int n) {
        int low = 1, high = n;
        while (low < high) {    // NOTE strict less than
            int mid = low + (high - low) / 2;
            if (isBadVersion(mid))
                high = mid;
            else
                low = mid + 1;
        }
     
        return low; // NOTE no minus 1

153	Find Minimum in Rotated Sorted Array

Binary Search, but  compare nums[mid] with nums[high]

while (low < high)

if nums[mid] > nums[high]

      low = mid + 1;

else

high = mid;

return nums[low]

33	Search in Rotated Sorted Array

Solution 1:
O(lgN) time and O(1) space, two passes
Use helper function findPivot() to binary search and find the minimum value index, which is the pivot index. ( i.e: 153 Find Minimum in Rotated Sorted Array). And then  do rotated binary search (i.e. realMid = (mid + pivot) % n).

 NOTE in step 2 binary search exit condition less than or equal, but in step 1,  finding a pivot index, strict less than is sufficient.


Solution 2:
O(lgN) time and O(1) space, One pass

A[mid] =  target, return mid，otherwise
(1) A[mid] < A[end]: A[mid+1 : end] sorted
A[mid] < target <= A[end]  right half，otherwise left half

(2) A[mid] > A[end] : A[start : mid-1] sorted
A[start] <= target < A[mid]  left half, otherwise right half

81	Search in Rotated Sorted Array II

 Same two 33 Search in Rotated Sorted Array, solution 2. But add two more lines two skip duplicate elements. O(lgN) average time and O(1) space, worst case O(N) time (all duplicate numbers)

      while (l < r && nums[l] == nums[l + 1])   l++; // skip duplicates from the left
       while (r > l && nums[r] == nums[r - 1]) r--; // skip duplicates from the right

50

Pow(x, n)

The naive O(N) solution would TLE

So the better binary search solution is O(lgN) recursion algorithm. i.e: cut the size n by half, and recursively call Pow(x, n/2), if n is even then res = half * half, otherwise res = half * half * x.  Note don't call myPow  Instead call once and save it to a temp and use it multiple times.

Note n could be negative in which case we need to get the absolute value of n, remember to use long type to hold value of n, and then get the absolute value of the long variable, only in that way, we won't have integer overflow problem.