Binary search is a searching algorithm that works efficiently with a sorted list, but it is still faster than linear search.
The mechanism of binary search can be better understood by an analogy of a telephone directory. When we are searching for a particular name in a directory, we first open the directory from the middle and then decide whether to look for the name in the first part of the directory or in the second part of the directory.
Again, we open some page in the middle and the whole process is repeated until we finally find the right name.
Now, let us consider how this mechanism is applied to search for a value in a sorted array. Consider an array A[] that is declared and initialized as
int A[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};and the value to be searched is VAL = 9. The algorithm will proceed in the following manner.
BEG = 0, END = 10, MID = (0 + 10)/2 = 5Now, VAL = 9 and A[MID] = A[5] = 5
A[5] is less than VAL(9), therefore, we now search for the value in the second half of the array. So, we change the values of BEG and MID
BEG = MID + 1 = 6, END = 10, MID = (6 + 10)/2 =16/2 = 8
VAL = 9 and A[MID] = A[8] = 8A[8] is less than VAL, therefore, we now search for the value in the second half of the segment. So, again we change the values of BEG and MID
Now, BEG = MID + 1 = 9, END = 10, MID = (9 + 10)/2 = 9
Now, VAL = 9 and A[MID] = 9
In this algorithm, we see that BEG and END are the beginning and ending positions of the segment that we are looking to search for the element. MID is calculated as (BEG + END)/2. Initially, BEG = lower_bound and END = upper_bound.
The algorithm will terminate when A[MID] = VAL. When the algorithm ends, we will set POS = MID. POS is the position at which the value is present in the array.
However, if VAL is not equal to A[MID], then the values of BEG, END, and MID will be changed depending on whether VAL is smaller or greater than A[MID].
- If VAL < A[MID], then VAL will be present in the left segment of the array. So, the value of END
will be changed as END = MID – 1. - If VAL > A[MID], then VAL will be present in the right segment of the array. So, the value of BEG
will be changed as BEG = MID + 1
Finally, if VAL is not present in the array, then eventually, END will be less than BEG. When this happens, the algorithm will terminate and the search will be unsuccessful.
Algorithm for Binary Search
Here is the complete algorithm for binary search
BINARY_SEARCH(A, lower_bound, upper_bound, VAL)
Step 1: [INITIALIZE] SET BEG = lower_bound
END = upper_bound, POS=-1
Step 2: Repeat Steps 3 and 4 while BEG <= END
Step 3: SET MID = (BEG + END)/2
Step 4: IF A[MID] = VAL
SET POS = MID
PRINT POS
Go to Step 6
ELSE IF A[MID] > VAL
SET END = MID-1
ELSE
SET BEG = MID+1
[END OF IF]
[END OF LOOP]
Step 5: IF POS=-1
PRINT “VALUE IS NOT PRESENT IN THE ARRAY”
[END OF IF]
Step 6: EXIT- In Step 1, we initialize the value of variables, BEG, END, and POS.
- In Step 2, a while loop is executed until BEG is less than or equal to END.
- In Step 3, the value of MID is calculated.
- In Step 4, we check if the array value at MID is equal to VAL (item to be searched in the array). If a match isfound, then the value of POS is printed and the algorithm exits. However, if a match is not found, and if the value of A[MID] is greater than VAL, the value of END is modified, otherwise if A[MID] is greater than VAL, then the value of BEG is altered.
- In Step 5, if the value of POS = –1, then VAL is not present in the array and an appropriate message is printed on the screen before the algorithm exits
C program for Binary Search
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define size 10 // Added to make changing size of array easier
int smallest(int arr[], int k, int n); // Added to sort array
void selection_sort(int arr[], int n); // Added to sort array
int main(int argc, char * argv[])
{
int arr[size], num, i, n, beg, end, mid, found = 0;
printf("\n Enter the number of elements in the array: ");
scanf("%d", & n);
printf("\n Enter the elements: ");
for (i = 0; i < n; i++) {
scanf("%d", & arr[i]);
}
selection_sort(arr, n); // Added to sort the array
printf("\n The sorted array is: \n");
for (i = 0; i < n; i++)
printf(" %d\t", arr[i]);
printf("\n\n Enter the number that has to be searched: ");
scanf("%d", & num);
beg = 0, end = n - 1;
while (beg <= end) {
mid = (beg + end) / 2;
if (arr[mid] == num) {
printf("\n %d is present in the array at position %d", num, mid + 1);
found = 1;
break;
} else if (arr[mid] > num)
end = mid - 1;
else
beg = mid + 1;
}
if (beg > end && found == 0)
printf("\n %d does not exist in the array", num);
return 0;
}
//Find the smallest from the array using this function
int smallest(int arr[], int k, int n) {
int pos = k, small = arr[k], i;
for (i = k + 1; i < n; i++) {
if (arr[i] < small) {
small = arr[i];
pos = i;
}
}
return pos;
}
//sorting array using Selection sort
void selection_sort(int arr[], int n) {
int k, pos, temp;
for (k = 0; k < n; k++) {
pos = smallest(arr, k, n);
temp = arr[k];
arr[k] = arr[pos];
arr[pos] = temp;
}
}Output:
Enter the number of elements in the array: 5
Enter the elements: 12 55 4 8 9
The sorted array is:
4 8 9 12 55
Enter the number that has to be searched: 12
12 is present in the array at position 4
That's it, we are done.
Complexity of binary search
The complexity of the binary search algorithm can be expressed as f(n), where n is the number of elements in the array. The complexity of the algorithm is calculated depending on the number of comparisons that are made. In the binary search algorithm, we see that with each comparison, the size of the segment where search has to be made is reduced to half. Thus, we can say that, in order to locate a particular value in the array, the total number of comparisons that will be made is given as 2f(n) > n or f(n) = log2n
Buy us a coffee
Become a Patron