VietMX Staff asked 4 years ago
When the list is sorted we can use the binary search (also known as half-interval search, logarithmic search, or binary chop) technique to find items on the list. Here’s a step-by-step description of using binary search:
- Let
min = 1andmax = n. - Guess the average of
maxandminrounded down so that it is an integer. - If you guessed the number, stop. You found it!
- If the guess was too low, set min to be one larger than the guess.
- If the guess was too high, set max to be one smaller than the guess.
- Go back to step two.
In this example we looking for array item with value 4:
When you do one operation in binary search we reduce the size of the problem by half (look at the picture below how do we reduce the size of the problem area) hence the complexity of binary search is O(log n). The binary search algorithm can be written either recursively or iteratively.
Complexity Analysis
Implementation
var binarySearch = function(array, value) { var guess, min = 0, max = array.length - 1; while(min <= max){ guess = Math.floor((min + max) /2); if(array[guess] === value) return guess; else if(array[guess] < value) min = guess + 1; else max = guess - 1; } return -1;}