# Binary Search

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

Last updated

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

Last updated

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

Always from `[0, n)`