Binary Search
Binary search is an efficient algorithm for finding a specific element in a sorted array or list. The key principle behind binary search is to divide the search interval in half with each step, significantly reducing the time it takes to find the target element compared to linear search, especially in large datasets. Here's a step-by-step explanation using an example with 10 elements:
Array: First, we need a sorted array. Let's say our array is
[1, 3, 4, 7, 9, 11, 12, 14, 17, 19]
, and we want to search for the number11
.Initial Variables: We start with two pointers, usually named
low
andhigh
. Initially,low
is set to the first index (0) andhigh
is set to the last index (9 in this case).Middle Element: We find the middle element of the array. The middle index,
mid
, is calculated as(low + high) / 2
. In our case, it's(0 + 9) / 2 = 4.5
, which we round down to4
. The middle element is the one at index 4, which is9
.Comparison: We compare the middle element with the target value (
11
). Since9
is less than11
, we discard the left half of the array including the middle element. Our new search space is[11, 12, 14, 17, 19]
.Update Pointers: We update
low
to bemid + 1
(which is now 5) and keephigh
as it is (9).Repeat Process: We repeat the process - find the middle of the new range, compare it with the target, and decide which half to keep. The new middle element is at index
(5 + 9) / 2 = 7
, which is14
.Comparison Again: Since
14
is greater than11
, we discard the right half of the current array. Our search space is now reduced to just[11]
.Final Step: We repeat the process. The middle of our new range
[11]
is11
, which matches our target.Conclusion: Since we've found the target, we conclude the search. If at any point our
low
exceedshigh
, it means the element isn't in the array.
Let's take another example of an array with 20 elements. Consider the sorted array:
[2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40]
Suppose we want to search for the number 26
.
Initial Array:
[2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40]
^ ^ ^
low mid high
Step 1: Since 26 > 20 (element at mid), discard left half including mid
[22, 24, 26, 28, 30, 32, 34, 36, 38, 40]
^ ^ ^
low mid high
Step 2: Since 26 < 30 (element at mid), discard right half including mid
[22, 24, 26, 28]
^ ^ ^
low mid high
Step 3: Since 26 > 24 (element at mid), discard left half including mid
[26, 28]
^
mid
Finally, we find 26 at mid.
Binary search halves the search space at each step, significantly reducing the number of comparisons needed to find the target or determine its absence. This makes binary search very efficient, especially for large datasets.
Let's write the pseudo-code for binary search and explain each step. The algorithm is applied on a sorted array.
Pseudo Code
function binarySearch(array, target)
low = 0
high = length(array) - 1
while low <= high
mid = (low + high) / 2
if array[mid] == target
return mid // Target found
if array[mid] < target
low = mid + 1 // Search in the right half
else
high = mid - 1 // Search in the left half
return -1 // Target not found
Explanation
Initialize Variables:
low
andhigh
are pointers to track the current search interval. Initially,low
is set to the start of the array (index 0), andhigh
is set to the end of the array (indexlength(array) - 1
).
Binary Search Loop:
- The
while
loop continues as long aslow
is less than or equal tohigh
, meaning there's still a range to search.
- The
Calculate Midpoint:
- The midpoint
mid
is calculated as the average oflow
andhigh
. This is the index we check against the target.
- The midpoint
Check Midpoint:
If
array[mid]
is equal to the target, the function returnsmid
. This means the target has been found.If
array[mid]
is less than the target, the target must be in the right half of the array. So, we setlow
tomid + 1
.If
array[mid]
is greater than the target, the target must be in the left half. So, we sethigh
tomid - 1
.
Target Not Found:
- If the loop exits without returning, it means the target is not in the array. We return
-1
or some other indicator of failure.
- If the loop exits without returning, it means the target is not in the array. We return
This algorithm is efficient for large datasets because it halves the search space with each step, having a time complexity of O(log n), where n is the number of elements in the array. However, it's crucial that the array is sorted before applying binary search.
Below is an example of a binary search algorithm implemented in C.
C Code for Binary Search
#include <stdio.h>
int binarySearch(int arr[], int size, int target) {
int low = 0;
int high = size - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid; // Target found
}
if (arr[mid] < target) {
low = mid + 1; // Search in the right half
} else {
high = mid - 1; // Search in the left half
}
}
return -1; // Target not found
}
int main() {
int arr[] = {2, 3, 4, 10, 14, 23, 31, 45, 56, 65};
int size = sizeof(arr) / sizeof(arr[0]);
int target = 23;
int result = binarySearch(arr, size, target);
if (result != -1) {
printf("Element is found at index %d\n", result);
} else {
printf("Element not found in the array\n");
}
return 0;
}
Explanation
Include Directive:
#include <stdio.h>
is used to include the Standard Input Output header file, which is required for using theprintf
function.The
binarySearch
Function:It takes three parameters: the array
arr
, itssize
, and thetarget
element to search for.Variables
low
andhigh
are initialized to mark the beginning and end of the array.A
while
loop runs as long aslow
is less than or equal tohigh
.Inside the loop,
mid
is calculated as the average oflow
andhigh
. To avoid potential overflow, it's calculated aslow + (high - low) / 2
instead of(low + high) / 2
.If
arr[mid]
is equal to the target, the function returns the indexmid
.If
arr[mid]
is less than the target, the search continues in the right half by settinglow
tomid + 1
.If
arr[mid]
is greater than the target, the search continues in the left half by settinghigh
tomid - 1
.If the target is not found, the function returns
-1
.
The
main
Function:Defines an array
arr
and its sizesize
.Specifies the
target
element to search for.Calls the
binarySearch
function and stores the result inresult
.Prints the index where the element is found or a message if it's not found.
Return Statement: The
main
function returns0
, indicating successful program termination.
Complexity analysis of the binary search algorithm involves examining both its time complexity and space complexity:
Time Complexity
Best Case: O(1)
- The best-case scenario occurs when the target element is at the midpoint of the array during the first iteration. In this case, only one comparison is needed, and the algorithm terminates immediately.
Average and Worst Case: O(log n)
In each step of binary search, the array is effectively halved. This means that the time to search the array grows logarithmically with the size of the array.
Mathematically, at most (\log_2 n + 1) comparisons are needed, where ( n ) is the number of elements in the array. This logarithmic growth makes binary search very efficient for large datasets.
Space Complexity
Iterative Approach (as in the provided C code): O(1)
The iterative version of binary search, like the one you have in the C code, has a constant space complexity because it uses a fixed amount of space (for variables
low
,high
,mid
, etc.) regardless of the input size.There are no additional data structures used that grow with input size.
Recursive Approach: O(log n)
- If binary search is implemented using recursion, the space complexity can become O(log n) due to the use of the call stack. Each recursive call adds a layer to the stack, and there can be up to (\log_2 n) calls in the worst case.
Binary search is highly efficient in terms of time complexity, especially compared to linear search, which has a time complexity of O(n). The space efficiency is also excellent in the iterative approach, making it a preferred method for searching in sorted arrays or lists.