Searching Algorithm
In this tutorial we will learn about Binary Search algorithm to search an item from a given set of items.
In this search technique we divide the given array into two halves at each level and look for the key element in one of the two halves.
This algorithm works only for sorted array.
It is similar to searching a word in a dictionary. We roughly start from the middle. If we are look for a word starting with let's say E then we discard the other half and look in the first half and repeat the process till we find the result.
/** * a[0:n-1] is an array of n elements. key is the element being searched. */ BinarySearch(a, n, key) Begin Set start = 0, end = n-1, mid = (start + end)/2; while( start <= end && a[mid] != key) do if (key < a[mid]) then Set end = mid – 1; //search in the left half else Set start = mid + 1; //search in the right half endif Set mid = (start + end)/2; endwhile if(start > end) return -1; //key not found return mid; //returning key index End
If there are n elements in a given array. Then in each level the array is halved and the search is reduced to one half of the array.
n
Therefore, if there are n elements then it will require floor(log2n+1) iterations.
floor(log2n+1)
So, we can write order as O(log2n).
#include <stdio.h> //function declaration int binarySearch(int *a, int n, int key); int main(){ //variable declaration int arr[10], i, key; //input printf("Enter elements of the array: "); for(i = 0; i < 10; i++) scanf("%d", &arr[i]); printf("Enter key: "); scanf("%d", &key); //search i = binarySearch(arr, 10, key); //output if(i == -1) printf("Key not found.\n"); else printf("Key at index: %d\n", i); return 0; } //function definition int binarySearch(int *a, int n, int key){ int start = 0, end = n - 1, mid = (start + end) / 2; while(start <= end && a[mid] != key){ if(key < a[mid]) end = mid - 1; else start = mid + 1; mid = (start + end) / 2; } if(start > end) return -1; //key not found return mid; }