Introduction
Binary search is an efficient search technique that uses the “Divide and Conquer” approach. This works by halving the number of elements each time until you get to the correct value.
It has a time complexity of O(logN).
How it works
The principle is quite basic:
- Look at the middle element of the array.
- If the number is lower than the middle element, then discard all the higher numbers. If the number is higher than the middle element, then discard the lower numbers.
- You can now repeat the above with the remainder of the numbers.
By repeating the above process, you will eventually land up with the number you were looking for through a process of elimination.
Note: Your array of items needs to be sorted for this method to work.
The example below is a way we can implement binary search.
We will use a variable called lowerBound to keep track of our lowest element and upperBound to keep track of our highest element.
We have added a few console.logs so you can understand what the binary search function is doing.
function binarySearch(array, valueToFind) {
let isValueFound = false;
let lowerBound = 1;
let upperBound = array.length;
while (!isValueFound) {
const midPoint = Math.floor(lowerBound + (upperBound - lowerBound) / 2);
console.log('-----');
console.log('lowerBound:', lowerBound, 'upperBound:', upperBound);
console.log('midPoint', midPoint);
if (array[midPoint] < valueToFind) {
lowerBound = midPoint + 1;
}
if (array[midPoint] > valueToFind) {
upperBound = midPoint - 1;
}
if (array[midPoint] === valueToFind) {
console.log('Found value:', valueToFind);
return midPoint;
}
}
}
const arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log('Binary search', binarySearch(arr, 9));
// -----
// lowerBound: 1 upperBound: 10
// midPoint 5
// -----
// lowerBound: 6 upperBound: 10
// midPoint 8
// -----
// lowerBound: 9 upperBound: 10
// midPoint 9
// Found value: 9
Lesson task
Binary search is a fairly simple principle which you should be able to reproduce once you gain an understanding of it.
Goal
To be able to do a Binary search.
Brief
- Complete the Level 1 process below.
NOTE: Lesson tasks do not get submitted on Moodle and are not assessed by tutors. They are mainly there for you to practise what you have learned in the lesson.
Level 1 process
-
Work through the code example above, trying to understand what each line is doing. If you don’t understand then console.log the values. Also go through the provided additional resources if you’re unclear.
-
Once you know how binary search works, try to create the algorithm yourself.