Intro
A common pattern, that utilizes a left and right pointer to half the list or array step by step.
// For BinarySearchTree see Trees.
How it works
- Start by checking if middle element is the target
- If yes then success and return
- If target is greater than middle, then set the left ptr to the element at the index of the middle + 1.
- If target is less than middle, then set the right ptr to the element at the index of the middle - 1.
Since we’re halving the search zone each time, it’s very efficient, with a time complexity of O(log(n))
Binary Search and Monotonic Functions
Can be used on any collection that utilizes a MonotonicFunction (function that either always increases or always decreases (or remains constant) over its entire domain) so can be used on any condition used for sorting, not just numbers.
Examples
- Binary Search in Arrays at Array Problems