Binary Search Time Complexity
Binary Search is a divide-and-conquer paradigm. It searches for an item in a sorted array. In this article, only sort ascending is considered. The item to search for is called the target value. The target value may or may not be found in the array.
The search begins by comparing the target value with the middle item of the sorted array. If the number of items in the array is even, then the item at half the number is considered the middle item. If the target value is the same as the middle item, then the target value index has been found. If they are not the same, then the target value is either larger or smaller than the middle item. If it is larger, then the lower half of the array will be abandoned for the search to continue in the upper half. If it is smaller, then the upper half of the array will be abandoned, for the search to continue in the lower half.
The search continues by dividing the half chosen into two again. A comparison between the target value and the middle item of this new half is made. If they are not the same, then this half is divided again into two and for the same reasons the previous half was divided. If the target value is not the same as the new middle item, then division continues.
When the target value and a median value (item) are the same, that is conquering. There and then, the search stops. If the target value is not in the array, the search will stop at some final middle item, which is not equal to the target value.
This article aims to give an appreciation called Time Complexity for the speed of Binary Search.
Article Content
- Introduction – see above
- Binary Search Illustration
- Time Complexity and Binary Search
- Coding in C
- Conclusion
Binary Search Illustration
Consider the sorted list:
Where the integer, 3, has to be searched. Of course, searching from the beginning will take three operations. However, using binary search will take four main operations as follows:
The target value is 3. Dividing the list into two makes 8 the middle item.
Is 8 the same as 3?
No. Since 3 is less than 8, the search will focus on the lower half. That is one main operation done.
Dividing into two again makes 4 the new middle item.
Is 4 the same as 3?
No. Since 3 is less than 4, the search will focus on the new lower half. That is the second main operation done.
Dividing into two again makes 2 the new middle item.
Is 2 the same as 3?
No. Since 3 is greater than 2, the search will then focus on the new upper half. That is the third main operation done.
Dividing into two again makes 3 the new middle item, of a half (sub-list) of length, one. The new and last middle item is now 3.
Is 3 the same as 3?
Yes. The target value has been found. That is the fourth and last main operation done.
When there are 16 items, a maximum of 4 main operations can be done. If there were 16 items, and the target value was in the range and could not be found, 4 main operations would still have taken place. For example, in the following list:
There are still 16 items. A target value of 3 would have ended at the value of 5, with still 4 main operations.
Time Complexity and Binary Search
Worst-Case Performance
Worst-case performance refers to the case where the target value is found at the last main operation, or the target value is in the range of values and is not found at the last main operation.
When the number of items is 16, the maximum number of operations will always be 4.
16 = 24
4 = log2(16)
Let n be 16. So,
4 = log2(n)
If n is 8, the maximum number of operations would be 3 = log2(8). If n is 32, the maximum number of operations would be 5 = log2(32).
The worst-case time complexity (relative speed) for Binary Search is said to be:
O(log2(n))
Where the big O and its parentheses having log2(n) is the notation for time complexity. It is simply written as:
O(log n)
Best-Case Performance
Assume that the target value was 8 for the first list above. In this case, the first main operation would have found the position of the target value. This is the best-case performance. The time complexity for this best-case performance is written as:
O(1)
Where 1 means one main operation.
Coding in C
A C code binary search function is:
int binarySearch(int arr[], int target, int n) {
int loIndex = 0;
int upIndex = n - 1;
// Make sure that we still have items in the list to search in
while (loIndex target) {
upIndex = middleIndx;
} else {
loIndex = middleIndx + 1;
}
}
// Return a negative number when we cannot find the target in the array
return -1;
}
The loIndex means the lowest index of a half (sub-list). The upIndex means the uppermost index of a half (sub-list). In the beginning, loIndex is 0 and upIndex is 15 when n is 16. The while-loop condition ensures that division continues until loIndex is the same as upIndex if the target value has not been found yet.
A suitable C main function for this code is:
{
int n = 16;
int target = 3;
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
int indexFound = binarySearch(arr, target, n);
printf("%d\n", indexFound);
return 0;
}
Conclusion
This article discussed the Binary Search time complexity and emphasized the following:
The worst-case time complexity for Binary Search is:
O(log n)
The best-case time complexity for Binary Search is:
O(1)
Source: linuxhint.com