Binary Search Algorithm
![Binary Search Algorithm Binary Search Algorithm](/images/binary-search.jpg)
What is Binary Search?
Binary Search, also known as half-interval search, logarithmic search, or binary chop is a searching algorithm that is used to search data in a sorted list. It is a divide and conquer algorithm that reduces the search space by half at every step.
How does Binary Search work?
Let's imagine we have a book with 24 pages and you want to go to a specific page, say page 18.
Click the circle numbered 18 below.
What did it do? It visited all 18 pages before reaching the desired page. This is how linear search works.
Now again click the circle numbered 18 below.
What did it do? It visited only 4 pages before reaching the desired page. This is how binary search works.
Algorithm
Step 1: Find the middle element of the list.
Step 2: Compare the middle element with the target element.
Step 3: If the middle element is equal to the target element, then return the index of the middle element.
Step 4: If the middle element is greater than the target element, then search the left half of the list.
Step 5: If the middle element is less than the target element, then search the right half of the list.
Step 6: Repeat steps 1 to 5 until the target element is found or the list is exhausted.
Pseudocode
Using this pseudocode, we can implement binary search in any programming language. Try to implement it in your favorite language and see if it works.
FUNCTION binary_search(SORTED_LIST[], TARGET)
SET LEFT TO 0
SET RIGHT TO LENGTH(SORTED_LIST) - 1
WHILE LEFT <= RIGHT DO
SET MIDDLE TO (LEFT + RIGHT) / 2
IF SORTED_LIST[MIDDLE] == TARGET THEN
RETURN MIDDLE
ELSE IF SORTED_LIST[MIDDLE] < TARGET THEN
SET LEFT TO MIDDLE + 1
ELSE
SET RIGHT TO MIDDLE - 1
END IF
END WHILE
RETURN -1
END FUNCTION
Implementation
We can implement binary search in two ways. One is iterative and the other is recursive. Let's implement both of them.
Binary Search using Iteration
Here is the iterative implementation of binary search in C, Java, Python, PHP, and JavaScript.
function binarySearch(sortedList, target, left, right) {
while (left <= right) {
let middle = Math.floor((left + right) / 2);
if (sortedList[middle] === target) {
return middle;
} else if (sortedList[middle] < target) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return -1;
}
let sortedList = [1, 2, 3, 4, 5, 6, 7];
let target = 5;
let left = 0;
let right = sortedList.length - 1;
let index = binarySearch(sortedList, target, left, right);
if (index === -1) {
console.log("Element not found");
} else {
console.log("Element found at index " + index);
}
function binarySearch($sortedList, $target, $left, $right) {
while ($left <= $right) {
$middle = floor(($left + $right) / 2);
if ($sortedList[$middle] === $target) {
return $middle;
} else if ($sortedList[$middle] < $target) {
$left = $middle + 1;
} else {
$right = $middle - 1;
}
}
return -1;
}
$sortedList = [1, 2, 3, 4, 5, 6, 7];
$target = 5;
$left = 0;
$right = count($sortedList) - 1;
$index = binarySearch($sortedList, $target, $left, $right);
if ($index === -1) {
echo "Element not found";
} else {
echo "Element found at index " . $index;
}
def binary_search(sorted_list, target, left, right):
while left <= right:
middle = (left + right) // 2
if sorted_list[middle] == target:
return middle
elif sorted_list[middle] < target:
left = middle + 1
else:
right = middle - 1
return -1
sorted_list = [1, 2, 3, 4, 5, 6, 7]
target = 5
left = 0
right = len(sorted_list) - 1
index = binary_search(sorted_list, target, left, right)
if index == -1:
print("Element not found")
else:
print("Element found at index", index)
public class BinarySearch {
public static int binarySearch(int[] sortedList, int target, int left, int right) {
while (left <= right) {
int middle = (left + right) / 2;
if (sortedList[middle] == target) {
return middle;
} else if (sortedList[middle] < target) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return -1;
}
public static void main(String[] args) {
int[] sortedList = {1, 2, 3, 4, 5, 6, 7};
int target = 5;
int left = 0;
int right = sortedList.length - 1;
int index = binarySearch(sortedList, target, left, right);
if (index == -1) {
System.out.println("Element not found");
} else {
System.out.println("Element found at index " + index);
}
}
}
#include <stdio.h>
int binary_search(int sorted_list[], int target, int left, int right) {
while (left <= right) {
int middle = (left + right) / 2;
if (sorted_list[middle] == target) {
return middle;
} else if (sorted_list[middle] < target) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return -1;
}
int main() {
int sorted_list[] = {1, 2, 3, 4, 5, 6, 7};
int target = 5;
int left = 0;
int right = sizeof(sorted_list) / sizeof(sorted_list[0]) - 1;
int index = binary_search(sorted_list, target, left, right);
if (index == -1) {
printf("Element not found\n");
} else {
printf("Element found at index %d\n", index);
}
}
Binary Search using Recursion
Here is the recursive implementation of binary search in C, Java, Python, PHP, and JavaScript.
function binarySearch(sortedList, target, left, right) {
if (left > right) {
return -1;
}
let middle = Math.floor((left + right) / 2);
if (sortedList[middle] === target) {
return middle;
} else if (sortedList[middle] < target) {
return binarySearch(sortedList, target, middle + 1, right);
} else {
return binarySearch(sortedList, target, left, middle - 1);
}
}
let sortedList = [1, 2, 3, 4, 5, 6, 7];
let target = 5;
let left = 0;
let right = sortedList.length - 1;
let index = binarySearch(sortedList, target, left, right);
if (index === -1) {
console.log("Element not found");
} else {
console.log("Element found at index " + index);
}
function binarySearch($sortedList, $target, $left, $right) {
if ($left > $right) {
return -1;
}
$middle = floor(($left + $right) / 2);
if ($sortedList[$middle] === $target) {
return $middle;
} else if ($sortedList[$middle] < $target) {
return binarySearch($sortedList, $target, $middle + 1, $right);
} else {
return binarySearch($sortedList, $target, $left, $middle - 1);
}
}
$sortedList = [1, 2, 3, 4, 5, 6, 7];
$target = 5;
$left = 0;
$right = count($sortedList) - 1;
$index = binarySearch($sortedList, $target, $left, $right);
if ($index === -1) {
echo "Element not found";
} else {
echo "Element found at index " . $index;
}
def binary_search(sorted_list, target, left, right):
if left > right:
return -1
middle = (left + right) // 2
if sorted_list[middle] == target:
return middle
elif sorted_list[middle] < target:
return binary_search(sorted_list, target, middle + 1, right)
else:
return binary_search(sorted_list, target, left, middle - 1)
sorted_list = [1, 2, 3, 4, 5, 6, 7]
target = 5
left = 0
right = len(sorted_list) - 1
index = binary_search(sorted_list, target, left, right)
if index == -1:
print("Element not found")
else:
print("Element found at index", index)
public class BinarySearch {
public static int binarySearch(int[] sortedList, int target, int left, int right) {
if (left > right) {
return -1;
}
int middle = (left + right) / 2;
if (sortedList[middle] == target) {
return middle;
} else if (sortedList[middle] < target) {
return binarySearch(sortedList, target, middle + 1, right);
} else {
return binarySearch(sortedList, target, left, middle - 1);
}
}
public static void main(String[] args) {
int[] sortedList = {1, 2, 3, 4, 5, 6, 7};
int target = 5;
int left = 0;
int right = sortedList.length - 1;
int index = binarySearch(sortedList, target, left, right);
if (index == -1) {
System.out.println("Element not found");
} else {
System.out.println("Element found at index " + index);
}
}
}
#include <stdio.h>
int binary_search(int sorted_list[], int target, int left, int right) {
if (left > right) {
return -1;
}
int middle = (left + right) / 2;
if (sorted_list[middle] == target) {
return middle;
} else if (sorted_list[middle] < target) {
return binary_search(sorted_list, target, middle + 1, right);
} else {
return binary_search(sorted_list, target, left, middle - 1);
}
}
int main() {
int sorted_list[] = {1, 2, 3, 4, 5, 6, 7};
int target = 5;
int left = 0;
int right = sizeof(sorted_list) / sizeof(sorted_list[0]) - 1;
int index = binary_search(sorted_list, target, left, right);
if (index == -1) {
printf("Element not found\n");
} else {
printf("Element found at index %d\n", index);
}
}
Performance of Binary Search
Time Complexity
The time complexity of binary search is O(log n). This is because the search space is reduced by half at every iteration.
At innitial iteration, the search space is n. At the next iteration, the search space is reduced to n/2. At the next iteration, the search space is reduced to n/4. This continues until the search space is reduced to 1.
The number of iterations required to reduce the search space to 1 is given by log n. Therefore, the time complexity of binary search is O(log n).
Space Complexity
Binary search is an in-place algorithm. Therefore, the worst-case space complexity of binary search is O(1).
Case | Time Complexity | Space Complexity |
---|---|---|
Best | O(1) | O(1) |
Average | O(log n) | O(1) |
Worst | O(log n) | O(1) |
Binary Search VS Linear Search
Binary search is much faster than linear search. Let's see how much faster it is.
Let's say have a sorted list of numbers 1 to 7 and we want to find the number 5 in it.
Using Binary Search Algorithm
So we start from the middle of the list which is 4. As 4 is not the number we are looking for we check if the number we are looking for is before or after 4.
5 is after 4 so we will eliminate the first half of the list and search in the second half.
Again we will start from the middle of the list which is 6. As 6 is not the number we are looking for we check if the number we are looking for is before or after 6.
5 is before 6 so we will eliminate the second half of the list and search in the first half.
Again we will start from the middle of the list which is 5. As 5 is the number we are looking for we will return the index of 5 which is 4.
To find the number 5 in the list we had to check 3 times.
Using Linear Search Algorithm
In the case of linear search, we will start from the first element of the list which is 1. As 1 is not the number we are looking for we will check the next element which is 2. 2 is not the desired number so we will keep checking the next element until we find the number 5.
To find the number 5 we will have to check 5 times.
If the list had 100 elements then in the case of linear search we would have to check 100 elements to find the desired number.
But in the case of binary search, we would have to check only 7 elements. So we can see that binary search is much faster than linear search.
Applications of Binary Search
Binary search is used to search data in a sorted list. It is used in many applications such as searching for a word in a dictionary, searching for a name in a phone book, searching for a number in a sorted list, etc.
Pros and Cons of Binary Search
Advantages of Binary Search
- Binary search is one of the fastest search algorithm.
- Binary search is an in-place algorithm and it doesn't require any extra space.
- Binary search is easy to implement.
Disadvantages of Binary Search
- Binary search can only be used to search data in a sorted list.
- Binary search is not suitable for searching data in a linked list.
Common Questions
Question: What is the time complexity of binary search?
Answer: The time complexity of binary search is O(log n).
Question: What is the space complexity of binary search?
Answer: The space complexity of binary search is O(1).
Question: What is a divide and conquer algorithm?
Answer: Divide and conquer algorithm is an algorithm that divides the problem into smaller sub-problems and solves them recursively. Then it combines the results of the sub-problems to solve the original problem.
Question: What is the difference between linear search and binary search?
Answer: Linear search is a searching algorithm that searches the list sequentially. Binary search is a searching algorithm that divides the list into two halves and searches the list recursively.
Conclusion
In this article, we learned about binary search and how it works, its complexity, and its applications. We also learned how to implement binary search in both recursive and iterative ways in different programming languages.
Hope this article was helpful. If you have any questions or suggestions, please leave a comment below.