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:

Preprocessing  Sort if collection is unsorted.

Binary Search  Using a loop or recursion to divide search space in half after each comparison.

Postprocessing  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(r1)*(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 postprocessing 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 = length1
Termination: left > right
Searching Left: right = mid1
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
 Postprocessing 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
 Postprocessing 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 = length1
 Termination:
left + 1 == right
 Searching Left:
right = mid
 Searching Right:
left = mid
This is the end of post