Binary Search

Binary search typically appears when the array is sorted or its left and right halves both possess the same properties

Runtime analysis

$$T(n)=T(\frac{n}{2})+O(1)=O(\log n)$$

Take note…

• Is array sorted?

  • If not, can you sort it and still preserve information?

• Can the array be separated into two distinct parts where the first half satisfies a condition while the other does not?

Techniques

Peak finding

Move towards the direction of larger/smaller values relative to the mid-point chosen.

• This does not work with arrays that can have duplicates (naively picking a direction to move in could be disastrous)

• This can only produce local peaks

Peak finding in rotated arrays

Rotated arrays refer to arrays where the values after index i are moved to the front of the array instead, preserving their order [1, 2, 3, 4, 5] can be rotated to become [3, 4, 5, 1, 2]

The arrays always exhibit the following properties:

• nums[0] > nums[-1]

• There are essentially 2 sorted arrays, the boundary can be found by comparing nums[i] against nums[0]

  • If nums[i] > nums[0], i is in the first half, otherwise, it is in the second half

Problems commonly test to see if you can identify these properties (such as Find Minimum in Rotated Sorted Array or Search in Rotated Sorted Array)

• Use nums[0] as a marker for determining where i is in the array

Apply binary search to matrices

Try using the values of the arrays as a range or treating using the pure index like (0, 0) to (n - 1, n - 1) has the last index as (n * n) - 1

• These problems are harder to notice but a common property that can be found is when the matrix is sorted in some order (row)

Problems can include searching a fully sorted 2D matrix or modifying binary search to search the matrix in a consistent manner such as Kth Smallest Element in a Sorted Matrix

General template

Template

left, right = 0, len(nums) - 1  # start to end of array
while left < right:  # terminates when left = right
	mid = left + (right - left) // 2  # avoids overflow
	if nums[mid] < target:  # mid is left leaning
		left = mid + 1  # mid cannot be the answer
	else:
		right = mid  # mid might be the answer
return left if nums[left] == target else -1

Variations

# Search for index of target, else -1 if target does not exist
def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi: # Use <= here since the target index could be at lo == hi
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] > target: # Mid is too large, move search space to left
            hi = mid - 1
        else: # Mid is too small, move search space to right
            lo = mid + 1
    return -1 # Not found

# Search for the smallest index i such that nums[i] >= target
def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo < hi: # not using <= since if our answer is at lo == hi, infinite loop occurs due to floor division
        mid = (lo + hi) // 2
        if nums[mid] >= target: # mid could be the index we want since nums[mid] >= target
            hi = mid 
        else: # nums[mid] < target, move search space to right
            lo = mid + 1
    return lo # smallest index i that satisfies nums[i] >= target if nums[lo] >= target. If nums[lo] < target, all numbers are < target.

# Search for largest index i such that nums[i] <= target
def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo < hi: # not using <= since if our answer is at lo == hi, infinite loop occurs
        mid = (lo + hi) // 2
        if nums[mid] <= target: # mid could be the index we want since nums[mid] <= target
            lo = mid 
        else: # nums[mid] > target, move search space to left
            hi = mid - 1
    return hi # largest index i that satisfies nums[i] <= target if nums[hi] <= target. If nums[hi] > target, all numbers are > target.

Range

Always from [0, n)

Condition

< vs <=

• Former is often used for approximate answers while latter is used for guaranteed answers

• Consider the case when l == r and we can still move, where would l be? Where would r be? Is that information useful to us?

• If <= used, must include the following to avoid infinite loop

  • Must track the answer internally

  • Must move pointers by m - 1 and m + 1 to avoid infinite looping

  l, r = i + 1, n - 1
  j = -1
  while l <= r:
      m = l + (r - l) // 2
      if values[m][0] >= values[i][1]:
          j = m
          r = m - 1
      else:
          l = m + 1

Pointer Shifts

mid is left leaning:

mid = left + (right - left) // 2

• Set right = mid and left = mid + 1

• Useful when dealing with cases where the right could also be the answer

• I.e. finding first instance of element

mid is right leaning:

mid = left + (right - left) // 2 + 1

• Set left = mid and right = mid - 1

• Useful when dealing with cases where left could also be the answer

• I.e. finding last instance of element

Return Value

Run through some examples to figure out where the left lies (usually we care only about left)

Considerations

• When do we move towards the left?

• When do we move towards the right?

• What assumptions can we make about the way the data is arranged?

• Does the middle element tell us anything about everything on the left/right?