# Collection of Binary Search Templates

## Contents

Binary Search is an algorithm that *divides the search space in 2* after every comparison. Binary Search should be considered every time you need to search for an index or element in a collection. If the collection is unordered, we can always sort it first before applying Binary Search.

## Three Parts of Binary Search

Binary Search is generally composed of 3 main sections:

**Pre-processing**- Sort if collection is unsorted.**Binary Search**- Using a loop or recursion to divide search space in half after each comparison.**Post-processing**- Determine viable candidates in the remaining space.

## Template #1

Include left range, but not include right range. `[l, r)`

1 | def binary_search(l, r): |

In this template, return the smallest number **m** in range `[l, r)`

so that `check(m)`

is **true**. Return `r`

if not found.

Time Complexity: `O(log(r-1)*(check(m)))`

Space Complexity: `O(1)`

## Template #2

Both include the left and right left. `[l, r]`

1 | def binary_search(l, r): |

In this template, return the smallest number **m** in range `[l ,r]`

so that `check(m)`

is **true**. Return `r`

if not found.

## Template #3

1 | def binarySearch(nums, target): |

Template #1 is the most basic and elementary form of Binary Search. Template #1 is used to search for an element or condition which can be determined by accessing a single index in the array.

### Key Attributes

- Most basic and elementary form of Binary Search
- Search Condition can be determined without comparing to the element’s neighbors (or use specific elements around it)
- No post-processing required because at each step, you are checking to see if the element has been found. If you reach the end, then you know the element is not found

### Distinguishing Syntax:

Initial Condition: `left = 0, right = length-1`

Termination: `left > right`

Searching Left: `right = mid-1`

Searching Right: `left = mid+1`

## Template #4

1 | def binarySearch(nums, target): |

Template #4 is an advanced form of Binary Search. It is used to search for an element or condition which requires accessing the current index and its immediate right neighbor’s index in the array.

### Key Attributes:

- An advanced way to implement Binary Search.
- Search Condition needs to access element’s immediate right neighbor
- Use element’s right neighbor to determine if condition is met and decide whether to go left or right
- Gurantees Search Space is at least 2 in size at each step
- Post-processing required. Loop/Recursion ends when you have 1 element left. Need to assess if the remaining element meets the condition.

### Distinguishing Syntax:

- Initial Condition:
`left = 0, right = length`

- Termination:
`left == right`

- Searching Left:
`right = mid`

- Searching Right:
`left = mid+1`

## Template #5

1 | def binarySearch(nums, target): |

Template #5 is another unique form of Binary Search. It is used to search for an element or condition which requires accessing the current index and its immediate left and right neighbor’s index in the array.

### Key Attributes:

- An alternative way to implement Binary Search
- Search Condition needs to access element’s immediate left and right neighbors
- Use element’s neighbors to determine if condition is met and decide whether to go left or right
- Gurantees Search Space is at least 3 in size at each step
- Post-processing required. Loop/Recursion ends when you have 2 elements left. Need to assess if the remaining elements meet the condition.

### Distinguishing Syntax:

- Initial Condition:
`left = 0, right = length-1`

- Termination:
`left + 1 == right`

- Searching Left:
`right = mid`

- Searching Right:
`left = mid`

*This is the end of post*