Binary Search is an algorithm that allows you to search for a value that you can reach by a target and this value may be the target.
Why do use Binary Search Algorithm and not Simple Search Algorithm?
Suppose you have an array containing 100 elements and you want to reach the 100th element. If we use the Simple Search algorithm, we will be able to reach the 100th element after 100 attempts. Whereas, if we use the Binary Search algorithm, we will be able to reach element 100 after about 6 attempts. It's a big difference!
This makes the Binary Search algorithm the best choice for large arrays.
How does the Algorithm work?
- The algorithm takes array and it will give the start position and it will be at the beginning of array (index 0) and the last position and it will be the last of array.
- The algorithm checks all the elements of the array and gives a position in the middle. It will always be between the beginning and the last.
- After completing the previous steps, the algorithm starts with its conditions:
A- If the center is equal to the target, then it is the desired element.
B- And if the middle is smaller than the target, it will make the value of the starting position is middle + 1 so (start = middle + 1).
C- And in the case that the middle is greater than the target, it will make the value of the last position is the middle - 1 so (last = middle - 1).
We can start with the code to make the idea more clear.
Binary Search Algorithm In JavaScript
function binary_search(arr, target) {
var start = 0;
var last = (arr.length-1);
while(start <= last) {
var middle = Math.floor((start+last)/2);
if(arr[middle] == target) {
return middle;
}
else if(arr[middle] < target) {
start = middle+ 1;
}
else if(arr[middle] > target) {
last = middle- 1;
}
}
return null;
}
var arr = [1, 2, 3, 5, 7, 9];
console.log(binary_search(arr, 5)); // output: 3
Binary Search Algorithm In Python
def binary_search(arr, target):
start = 0
last = len(arr)-1
while start <= last:
middle = (start + last)//2
if arr[middle] == target:
return middle
elif arr[middle] < target:
start = middle + 1
elif arr[middle] > target:
last = middle - 1
return None
arr = [1, 2, 3, 5, 7, 9]
print(binary_search(arr, 3)) # output: 2
Time Complexity
- Simple Search: O(n) - linear time
- Binary Search: O(log n) - log time
That's it, folks! hope it was a good read for you. Thank you!