The program simply searches an element in the given array. There are two searching algorithms, linear search and binary search to achieve this functionality.
Binary Search
Binary search is a searching algorithm to find the given value within an array. This algorithm only works if the given array is already sorted. So that it canĀ figure out whether the given element exists or not.
It works by dividing a list into two halves and compare the middle element with the desired value.
If the value doesn’t match, the half in which the desired value can’t be present gets eliminated and again the remaining one is split down from the middle and that middle term again compared. It is repeated until a match is not found.
It requires O(log n) running time to search an element in the worst case scenario. It is also known as half-interval search.
Pseudocode
first=0 last=Array.Length -1 WHILE first<= last mid= (first+last)/2 IF arr[mid]== element return mid ELSE IF arr[mid]> element last=mid-1 ELSE first=mid+1 END IF END IF END WHILE
C program to search an element using binary search
#include<stdio.h> #include<math.h> int Binary_Search(int arr[], int element,int size) { int pos=-1,mid,first,last; first=0; last=size-1; while(first<= last) { mid= (first+last)/2; if(arr[mid]== element) { pos = mid; break; } else if(arr[mid]>element) last=mid-1; else first=mid+1; } return pos; } int main() { int arr[]={1,2,3,4,5}; int i,pos,element; printf("\n Please enter an element to search in list: "); scanf("%d",&element); pos =Binary_Search(arr,element,5); if(pos!=-1) printf("\n your element found at : %d position and the number was %d ", pos+1,arr[pos]); else printf("element is not found"); return 0; }
Output:
How does Binary search work ?