![Binary Search Algorithm & Time Complexity [2024]](/__khugblog-next/image/?url=https%3A%2F%2Fd14b9ctw0m6fid.cloudfront.net%2Fugblog%2Fwp-content%2Fuploads%2F2019%2F07%2FBlog_FI_July_upGrads-Knowledge-base.png&w=1920&q=75)
In programming languages, we search arrays by implementing two methods — Linear Search and Binary Search. Searching simply refers to finding a specific element from a list of elements linked to an array.
Linear search involves sequentially checking every element of a given list repeatedly until the element in question is found, or the algorithm is through with the list. On the other hand, binary search works by dividing a given list into two halves and comparing each item to the list’s middle element. Both algorithms are essential aspects of programming where arrays are concerned. However, binary search is more time-efficient and easily executable when we have a sorted list.
This post aims to paint a clear picture of binary search and its time complexity with respect to different cases.
What is Binary Search?
Binary search is one of the more commonly used techniques for searching data in arrays. You can also use it for sorting arrays. The principle of binary search is straightforward. It repeatedly divides the elements of an array into two halves with every iteration. The search logic checks whether the specified value is less than the middle item of the array and accordingly ignores the half in which the value is not present. This process happens in a loop until the correct value is located. Here are the steps involved in the binary search:
- Comparing the given item with the middle item of the array.
- If it matches with the middle element, then the program returns the middle element as the answer.
- If the unknown element is lesser than the middle element, we search the left half.
- If the unknown element is greater than the middle element, search the right half.
- This entire cycle repeats until we find the wanted element.
It should be noted that the user needs to sort the address before searching any element for accurate results.
Binary search, in practice, is more efficient than linear search. However, one needs to specify the order in which division of the array will occur.
What are the Different Types of Binary Search?
Binary search can be implemented in two ways based on the space complexity of the binary search algorithm:
- Recursive Binary Search
- Iterative Binary Search
Recursive Binary Search
In this method, there are no iterations or loops used to control the flow of the program. The maximum and minimum values are utilized as the boundary conditions.
The space complexity of this method is O(log n).
Here is a code snippet for a recursive binary search using C
#include <stdio.h>
int binary_Search(int array[], int x, int start, int end)
{
if (end >= start)
{
int midIndex = start + (end – start) / 2;
if (array[midIndex] == x)
return midIndex;
if (array[midIndex] < x)
return binary_Search(array, x, start, midIndex – 1);
return binary_Search(array, x, midIndex + 1, end);
}
return -1;
}
int main(void)
{
int array[] = {21, 45, 56, 6, 17, 28, 95};
int n = sizeof(array) / sizeof(array[0]);
int x = 45;
int answer = binary_Search(array, x, 0, n – 1);
if (answer == -1)
printf(“Element not present”);
else
printf(Answer: %d”, answer);
return 0;
}
Output:
Answer: 1
Iterative Binary Search
In this method, a loop is employed to control the iterations.
The space complexity is O(1) for the iterative binary search method.
Here is a code snippet for an iterative binary search using C:
#include <stdio.h>
int Binary_Search( int array[], int x, int start, int end)
{
while (start <= end) {
int midIndex = start + (end – start) / 2;
if (array[midIndex] == x)
return midIndex;
if (array[midIndex] > x)
start = midIndex + 1;
else
end = midIndex – 1;
}
return -1;
}
int main(void) {
int array[] = {12, 35, 56, 15, 127, 85, 17};
int n = sizeof(array) / sizeof(array[0]);
int x = 45;
int answer = Binary_Search(array, x, 0, n – 1);
if (answer == -1)
printf(“Element not present”);
else
printf(“Answer: %d”, answer);
return 0;
}
Output:
Answer: “Element is not present”
Dry run of Binary Search Algorithm
Item to be searched is 7
|
0 | 1 | 2 | 3 | 4 |
| 7 | 21 | 37 | 45 |
58 |
beg=0, end=4, mid=2
|
0 | 1 | 2 | 3 | 4 |
| 7 | 21 | 37 | 45 |
58 |
beg=0, end=1, mid=0
|
0 | 1 | 2 | 3 | 4 |
| 7 | 21 | 37 | 45 |
58 |
Element is found at index 0. Therefore, 0 will get returned.
What is Binary Search Time Complexity?
There are three-time complexities for binary search:
- O(1) – O(1) means that the program needs constant time to perform a particular operation like finding an element in constant time, as it happens in the case of a dictionary.
- O(n) – O(n) means that the time depends on the value of n. it is directly proportional to the operation’s duration of searching an element in the array of n elements.
- O(log n) – O(log n) is used in cases where we use recursive functions. The time complexity is dependent on the number of times the loop runs until it breaks. Unlike the previous one, it is not reliant on n but dependent upon the number of times the loop operates.
Here’s an understanding of binary search time complexity in detail:
|
Cases |
Time Complexity |
| Best Case: the result is returned in the first iteration |
O(1) |
| Average Case: the result is returned in three/four/average number of iterations |
O(logn) |
| Worst Case: the result is produced at the last comparison |
O(logn) |
Best Case Time Complexity
The best time complexity of binary search occurs when the required element is found in the first comparison itself, and only one iteration occurs. Therefore we use O(1). Essentially for this case, the element needs to be in the exact middle of the list because, in binary search, the first competition occurs with the middle element. Once the middle element does not return the correct answer, the iteration begins for the lesser half of the greater half.
Average Case Time Complexity
Taking an example of n distinct numbers (s1, s2, s3, …..s(n-1), sn), there can be two scenarios:
- Required element is present between index 0 to (n-1).
- Required element is not present in the given list from index 0 to (n-1).
So, there are n+1 separate cases that we need to take into consideration.
If the required element is present in index Y, then the program performing Binary Search will perform Y+1 comparisons, as:
The element at index n/2 returns in the first comparison (as Binary Search starts from the middle element, as in the case of Best time complexity).
Similarly, the 2nd comparison returns the elements at index n/4 and 3n/4 since their outcomes are based on the result of the 1st comparison.
According to this, we can conclude:
- Elements that need 1 comparison: 1
- Elements that need 2 comparisons: 2
- Elements that need 3 comparisons: 4
Therefore, elements that need t comparisons: 2^(t-1)
The maximum number of iterations = (Number of times n is divided by 2 so that result is 1) = logN comparisons.
t can vary from 0 to logn.
Total comparisons occuring = 1 * (Elements that need 1 comparison) + 2 * (Elements that need 2 comparisons) + … + logn * (Elements that need log n comparisons)
Total comparisons occuring = 1 * (1) + 2 * (2) + 3 * (4) + … + logn * (2^(logn-1))
Total comparisons occuring = 1 + 4 + 12 + 32 + … = 2^logn* (logn – 1) + 1
Total comparisons occuring = n * (logn – 1) + 1
Total number of cases = n+1
Therefore, average number of comparisons = (n*(logn-1)+1) / (n+1)
Average number of comparisons = n * logn / (n+1) – n/(n+1) + 1/(n+1)
The dominant term is n* logn / (n+1), which is approximately logn.
Thus, we can conclude that the average case Time Complexity of Binary Search is O(logN).
Worst Case Time Complexity
The worst time complexity of binary search occurs when the element is found in the very first index or the very last index of the array. For this scenario, the number of comparisons and iterations required is logn, where n is the number of elements in the array. It is called the worst time complexity because it consumes a lot of time for large arrays containing hundreds and thousands of values. Accordingly, hundreds and thousands of iterations must occur.
Conclusion
With global digitization scaling rapidly, learning programming languages is the need of the hour. Binary search is a pivotal tool that finds its usage in programming across languages. With a clear understanding of how these searches occur and the related load on the compiler, developers can write easily-executable codes such that the project does not encounter any bugs. Thus, understanding binary search complexities is a foundation stone for anyone looking forward to improving their coding skills.
We hope this post has provided a clear understanding of the same.
If you’d like to learn about binary search tree time complexities, join upGrad’s 20-months Master of Science in Machine Learning & Artificial Intelligence offered in collaboration with IIIT Bangalore & LJMU. The program syllabus is curated by reputed faculty and industry experts and includes 25+ mentorship sessions, 12+ industry projects, and 6 capstone projects, as well as 360-degree career support. Students get access to top global job opportunities on completion of the course.
Learn Machine Learning courses online from the World’s top Universities – Masters, Executive Post Graduate Programs, and Advanced Certificate Program in ML & AI to fast-track your career.
Go ahead and book your seat today!
