Binary search in Data Structures

Ratings:
(4)
Views:805
Banner-Img
  • Share this blog:

Binary search

The binary search in data structures is yet another simple method. However in the binary search, the algorithm expect the list to be sorted you can apply any one of the sorting methods before using the binary search algorithm. In binary search the given list is devided into two equal half’s. The given key is compared with the middle element of the list now three situations may occur. The middle element matches with the key the search will end peacefully here. The middle element is greater than the key then the value which we are searhing is possibly in the first half of the list. The middle element is lower than the key. Then the value which were searching is possibly in the second half of the list   Now the list is searched either in the first half is in the second half of got by the result of conditions (b) and (c) given above. This search fails because the key does not exist   21   Mid= left+right/2 Mid= 0+9/2 = 4.5   Program Binary search # include <stdio.h> # include <conio.h> void main() \{ int a[20],n,key,p,i; clrscr(); printf(“Enter the total number of elements \n”); scanf(“%d”,&n); printf(“Enter the element in ascending order \n”); for(i=0;i<n;i++) { scanf(“%d”,&a[i]); } printf(“Enter the search element \n”); scanf(“%d”,&key); p=binary search(a,n,key);     /* Functional */ if(p>=0) { printf(“search is successful \n”); printf(“The element found at position %d”,p+1); } else { printf(“search is unsuccessful search \n”); } else { printf (“search is unsuccessful search \n”); } } int binary search(int a[20],int n, int key) { int left, right, mid; left=0; right=n-1; while(left<=right) { mid=(left+right)/2; if(key==a[mid]) { right=mid-1; } else { left=mid+1; } } } return(-1); }   Time complexity: Each step at the algorithm divides the list divided into two parts and the search continues in one of them and the other is discarded the search requires at mast k steps where 2k > =N which results k=log2N thus the running time c both average and worst case of binary search is proportional  

You liked the article?

Like : 0

Vote for difficulty

Current difficulty (Avg): Medium

Recommended Courses

1/15

About Author
Authorlogo
Name
TekSlate
Author Bio

TekSlate is the best online training provider in delivering world-class IT skills to individuals and corporates from all parts of the globe. We are proven experts in accumulating every need of an IT skills upgrade aspirant and have delivered excellent services. We aim to bring you all the essentials to learn and master new technologies in the market with our articles, blogs, and videos. Build your career success with us, enhancing most in-demand skills in the market.


Stay Updated


Get stories of change makers and innovators from the startup ecosystem in your inbox