How to Implement Binary Search
Learn how to write an O(log N) binary search algorithm to instantly find elements in a sorted array.
Verify the Array is Sorted
Binary search uses a 'Divide and Conquer' strategy, which absolutely requires the data to be pre-sorted. If it is not sorted, you must sort it first or use a linear search.
Initialize the Search Boundaries
Create two pointers. Set 'LOW' to index 0 (the beginning of the array). Set 'HIGH' to index N - 1 (the end of the array).
Calculate the Safe Midpoint
Inside a while loop (LOW <= HIGH), calculate the middle index. To prevent integer overflow in strongly typed languages, use the formula: MID = LOW + (HIGH - LOW) / 2.
Check for a Match
Evaluate the element at array[MID]. If it equals your target value, you have successfully found the item. Return the MID index immediately.
Discard the Left Half
If array[MID] is less than your target, the target must reside in the right half of the array. Update LOW to MID + 1 to discard everything to the left.
Discard the Right Half
If array[MID] is greater than your target, the target must reside in the left half. Update HIGH to MID - 1 to discard everything to the right.
Handle the Not Found Case
If the loop finishes and LOW exceeds HIGH, the search space has collapsed to zero. Return -1 to indicate the target does not exist in the array.
Ready to master this completely?
Want to upskill yourself, crack your next interview, and get your dream job? Join our comprehensive course to dive deeper with high-quality video tutorials, solve interview questions, and a premium community.
