Given an an array of sorted numbers, write a function to search a given number in the array.
For example, if you're given the following sorted array:
arr = [1, 3, 5, 6, 7, 8, 9]
A search for
True, while a search for
How Binary Search works
Binary search of a number works on a sorted array by removing half of the array on each step.
First we start with the middle number. If the target number is greater than the middle number, then we know the target number is in the left half of the array.
Otherwise, our target number is in the right half.
We repeat these steps until we either find our target number or have eliminated the entire array.
Step through these steps visually below:
Since the problem is cut in half in each step, the time complexity of binary search is
Before you look at the solution, try to implement it yourself.