Half You Heard?
Searching Algorithms — Binary Search: Technique I
Binary search optimizes algorithms that need to search for an index or element in a sorted collection. Problems like these could be solved with a linear search, which produces a time complexity of O(n). Binary search improves the time complexity to O(log n) because the collection size is halved after each comparison.
In this pattern, the target value (e.g. 37) is compared to the middle element of the collection. If there is a match, the index is returned. If there is not a match, half of the collection is eliminated. Then, the target value is compared to the middle element of the remaining subsection. If there is not a match, this continues until there is no subsection left to search.
The next searchable subsection is determined by whether the target value is greater than or less than the middle element.
If the target value is:
- less than the middle element, the subsection to the left of the middle element is searched next.
- greater than the middle element, the subsection to the right of the middle element is searched next.
But, That’s Just The Half of It
This pattern uses three pointers to keep track of indices. Two pointers keep track of the searchable subsection: one pointer starts from the beginning of the collection (e.g. low) and the other pointer starts from the end of the collection (e.g. high). The third pointer keeps track of the index of the middle element (e.g. mid).
With each iteration:
- the mid pointer is set to a new value
- if a match is not found, either the low OR the high pointer is set to a new value, creating the next searchable subsection
Middle Element
The index of the middle element (mid) is set to the largest integer less than or equal to the median of low and high.mid = Math.floor((low + high) / 2)
Next Searchable Subsection
If the target value is:
- less than the middle element, the high pointer is set to the index of the element just left of the middle element.
high = mid - 1 - greater than the middle element, the low pointer is set to the index of the element just right of the middle element.
low = mid + 1
The pointers are moved until either a match is found or there is not a searchable subsection left.
Let’s Half at It
JavaScript Example
Sample Problems
Half a Nice Day!
📚 Resources 👀
Leetcode Explore — Binary Search
Udemy — JavaScript Algorithms and Data Structures Masterclass
