# Binary Search

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

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

- 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?

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

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

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

Template

Variations

1

left, right = 0, len(nums) - 1 # start to end of array

2

while left < right: # terminates when left = right

3

mid = left + (right - left) // 2 # avoids overflow

4

if nums[mid] < target: # mid is left leaning

5

left = mid + 1 # mid cannot be the answer

6

else:

7

right = mid # mid might be the answer

8

return left if nums[left] == target else -1

# 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

Condition

Pointer Shifts

Return Value

Considerations

Always from

`[0, n)`

`<`

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 - 1j = -1while l <= r:m = l + (r - l) // 2if values[m][0] >= values[i][1]:j = mr = m - 1else:l = m + 1

`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

Run through some examples to figure out where the

`left`

lies (usually we care only about `left`

)- 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?

Last modified 2mo ago