Binary Search

1. Finding the first and last appearance:

   1. Setting the i <= j:

   2. Exclude left sliding through (find the first appearance): left = mid - 1 (include "=", return right in the end)

   3. Exclude right sliding through (find the last appearance): right = mid + 1 (include "=", return left in the end)

   4. if search value: i<=j should care that the terminal index is not the answer if the target falls out of range of the search space

2. Find peak element:

   1. Finding two mid points: mid, mid + 1, compare:

   2. if num[mid1] < nums[mid2[: low = mid2

   3. else high = mid1

3. Trail and test (adopting 1)

   1. for certain criteria: if >=: l slide through mid to mid +1, return r (or <= r slide thorugh to mid -1, return l)

4. Search value in a rotated sorted array (distinct):

   1. if nums[mid] hits the value. return the mid index

   2. Find the continuous increasing part (whether nums[i] < nums[mid], or >, slide thru to mid+1 if ==.

   3. Comparing whether targets fall into the continuous part:

      1. nums[i] < nums[mid]: if nums[i] <= target < nums[mid]: assign j = mid - 1; else assign i = mid + 1 (go to the discontinuous part)

      2. nums[i] > nums[mid] (right part continuous): if nums[mid] < target <= nums[j]: assign i = mid + 1; else assign j = mid - 1

      3. nums[i] == nums[mid] : just sliding through to i = mid + 1 since nums[mid] != target

   4. return -1 (if search failed)

5. Search value in a rotated sorted array (duplicates)

   1. only difference: handling cases of == among nums[i]. nums[j], nums[mid]: if nums[i] == nums[mid] == nums[j]: move both i and j. (i++/j--); else if only nums[i] == nums[mid]: i sliding through to mid + 1: i = mid + 1. In this case, leaving no space for nums[i] == nums[mid]

   2. Only leave cases where: nums[i] < nums[mid] (test nums[i] <= target < nums[mid]); or nums[i] > nums[mid] (test nums[mid] < target <= nums[j])

6. Find minimum in a rotated sorted array:

   1. Assumption: exists, no duplicates

      1. selecting right as the comparison nums[mid[ vs nums[right] because natually the number increases from left to the right -> if nums[mid] > nums[right] -> there MUST BE a pivot on (mid, right] so we can throw our left and directly go left = mid + 1. We cannot draw similar conclusion on the left since if nums[mid] > nums[left] : we cannot infer there is a pivot in [left, mid).

   2. Assumption: exists, DUPLICATES: 1. similar to case before: except handling the duplicates: if (nums[mid] == nums[right]) right-= 1;

7. Find first and last position

   1. M1: search a float point approach: search (target - 0.5) and (target+ 0.5) instead: found the first upper bound for query value

   2. Standard solution:

      1. Search for the first appearance:

         1. Condition: i < j -> (so check [i]([j])) in the end

         2. mid = (i + j) /2; i = mid + 1; j = mid;

      2. Search for the last appearance

         1. Condition i < j without check since already checked

         2. mid = (i + j + 1) /2 since we need to preserve the mid from the left if nums[mid] == target -> i = mid -> we need to bias the mid to the right to prevent being stuck.

8. Search in a 2D partial ordering:

   1. Use Trail and Error to find the upper bound (number that are <= than [mid]) in order to deal with duplicates. for each search:

   2. Start with "middle" point: the point that has the largest value in one dim and least value in another dim. (This helps opt out less optimal solution after the comparison)

   3. With Heap: Maintaining n candidates: initialized by the first column: Each time a value pops out, add in its "children" the value at the same column index but at the next row (if there is)

9. Search in a window: (Find k closest)

   1. Find the optimal starting point i that [i] < [i + k]