Sometimes the best ways to learn something is by showing an example.
Let's say we are given a problem below problem and we are told to find 37 using binary search. See the visual representation of the process below
Let's say we are given a problem below problem and we are told to find 37 using binary search. See the visual representation of the process below
The steps are as follow:
- You set the left and right index
- Find the mid-point
- Checks:
- If target is equal to the midpoint, we have found our target
- If target is greater than the mid-point, shift left point to mid-point + 1 (removes 1 to 19 from above example)
- If target is less than the midpoint, shift right to mid-point
- repeat until target is mid-point
- if target can't be found return -1
This simple lines of code can be used to solve a variety of binary search problems. For examples:
- Search Insert Position (Leetcode 35) by change last line to left
- First Bad Version (Leetcode 278) by changing last line to left and the condition of the if else logic