Binary Search
Algorithm · Core
Step through it: Modified Binary Search pattern
target = 23
Step 1 of 6
Goal: find 23 in this sorted list. Checking one number at a time could take 7 looks, and a million numbers would take up to a million. Because the list is sorted, we can do far better.
Step 2 of 6
Look at the middle number first. The middle of positions 0 to 6 is position 3, which holds 12.
Step 3 of 6
12 is smaller than 23, and the list is sorted, so 23 cannot be at or before 12. Throw away that whole half. Only positions 4 to 6 are left.
Step 4 of 6
Do the same thing on what is left. The middle of positions 4 to 6 is position 5, which holds 23. Found it.
Step 5 of 6
Two looks instead of up to seven. Every look halves what is left, so a million numbers need only about 20 looks. Halving the search area each time is called binary search.
Step 6 of 6
Your turn. Pick a target and press Next to watch each look. Try 7: it is not in the list.
Complexity
Time Complexity
O(log(n)) - since we split search area by two for every
next iteration.
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful. If the search ends with the remaining half being empty, the target is not in the array.
Code
import Comparator from '../../../utils/comparator/Comparator';
/**
* Binary search implementation.
*
* @param {*[]} sortedArray
* @param {*} seekElement
* @param {function(a, b)} [comparatorCallback]
* @return {number}
*/
export default function binarySearch(sortedArray, seekElement, comparatorCallback) {
// Let's create comparator from the comparatorCallback function.
// Comparator object will give us common comparison methods like equal() and lessThan().
const comparator = new Comparator(comparatorCallback);
// These two indices will contain current array (sub-array) boundaries.
let startIndex = 0;
let endIndex = sortedArray.length - 1;
// Let's continue to split array until boundaries are collapsed
// and there is nothing to split anymore.
while (startIndex <= endIndex) {
// Let's calculate the index of the middle element.
const middleIndex = startIndex + Math.floor((endIndex - startIndex) / 2);
// If we've found the element just return its position.
if (comparator.equal(sortedArray[middleIndex], seekElement)) {
return middleIndex;
}
// Decide which half to choose for seeking next: left or right one.
if (comparator.lessThan(sortedArray[middleIndex], seekElement)) {
// Go to the right half of the array.
startIndex = middleIndex + 1;
} else {
// Go to the left half of the array.
endIndex = middleIndex - 1;
}
}
// Return -1 if we have not found anything.
return -1;
}References
Practice
Modified Binary Search
- Binary SearchEasy
- Search Insert PositionEasy
- Sqrt(x)Easy
- First Bad VersionEasy
- Valid Perfect SquareEasy
- Arranging CoinsEasy
- Search in Rotated Sorted ArrayMedium
- Find Minimum in Rotated Sorted ArrayMedium
- Find First and Last Position of Element in Sorted ArrayMedium
- Find Peak ElementMedium
- Search a 2D MatrixMedium
- Koko Eating BananasMedium
- Capacity To Ship Packages Within D DaysMedium
- Time Based Key-Value StoreMedium
- Single Element in a Sorted ArrayMedium
- Minimum Number of Days to Make m BouquetsMedium
- Median of Two Sorted ArraysHard
- Split Array Largest SumHard
- Find Minimum in Rotated Sorted Array IIHard
Divide & Conquer
- Majority ElementEasy
- Convert Sorted Array to Binary Search TreeEasy
- Pow(x, n)Medium
- Sort ListMedium
- Maximum SubarrayMedium
- Different Ways to Add ParenthesesMedium
- Construct Quad TreeMedium
- Kth Largest Element in an ArrayMedium
- Merge k Sorted ListsHard
- Reverse PairsHard
- The Skyline ProblemHard
- Median of Two Sorted ArraysHard
Spotted a mistake or something unclear? Report it on GitHub.