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]

Last updated

Was this helpful?