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

Range

Always from [0, n)

Condition

Pointer Shifts

Return Value

Considerations