In this tutorial you will learn about the Binary Search Algorithm and its application with practical example.
What Is Binary Search Algorithm?
Binary search is one of the commonly used search algorithm in data structure. The Binary search is an efficient search algorithm for finding an item in a sorted list of items. Binary search algorithm works only on a sorted list of elements. In order to search an element using binary search algorithm, we must ensure that the list is sorted. When binary search is performed with a sorted list, the number of iterations can be reduced significantly.
How Binary Search Algorithm Works
Binary search algorithm is based on divide and conquer approach. In Binary search, an item is searched by comparing middle most element of the sorted list. If the search item is matched with the middle element of the list, then it returns the index of matched element. Otherwise, we check whether the given search item is smaller or larger than the middle element of the list. If the search item is smaller, then we will repeat this search process in the left sub-list to find the item. If the search item is greater, then we will repeat this search process in the right sub-list to find the item.
At each step, we have reduced search space to find the target value because the list is sorted, We repeat this process until we find the search item in the list or we left with a sub-list consisting of a single element. And if the search item is not found in list then the “Search Item not found.” result is displayed.
Binary Search Program In C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include <stdio.h> int main() { int a[100], search, ctr, n, first, last, middle; printf("Enter number of elements in array:\n"); scanf("%d", &n); printf("Enter %d integer numbers:\n", n); for (ctr = 0; ctr < n; ctr++) scanf("%d", &a[ctr]); printf("Enter a number to search:\n"); scanf("%d", &search); first = 0; last = n - 1; middle = (first+last)/2; while (first <= last) { if (a[middle] < search) first = middle + 1; else if (a[middle] == search) { printf("%d is found at location %d.\n", search, middle+1); break; } else last = middle - 1; middle = (first + last)/2; } if (first > last) printf("%d is not present in the list.\n", search); return 0; } |
Output:-
