Binary Search

Searching—Finding the specified record(s) in a given data structure on the basis of a given key value. Binary search is the method used for searching. For Example there are 100 employees working in the company and we have to give the increment only that employee whose employee number is 101, so this operation can be used to find the  employee detail with employee number 101.

In case of Binary search the first need is to sort the data in array due to  binary search work on sorted array. With the help of sorted element array we can search required data from the array very quickly.

In binary search the array list is divided into 2 equal parts.

 

  •       Suppose that   the  elements  of array are in ascending order then if the desired element is less than the middle element of array list, it will never be present in the second half of the array.
  •        Similarly  if it is greater than the middle element of array, it will never  be present in the first half.
  •        So, we can search element from only one half of the array list.
  •        This  process  is repeated and in the next stage we have to search the element only in one quarter of the array.
  •        This process reduces the length of the search and search time.
  •       The process is repeated again & again until the element is found(search is successful or element not found, search is unsuccessful).
  •       Binary search is extremely efficient search algorithm, that can be used to find the location of a given element data in the array list.

Algorithm……..Binary Search

SA, LBD, UBD, ITEM, LOC, BEGN, END, MID

SA…..is Sorted Array

LBD…..is Lower Bound

UBD….is Upper Bound

ITEM…. Stores the value to be searched.

BEGN…..beginning location of array SA

END…..end location of array SA

MIDDLE…..middle location of array SA

This algorithm  finds the location(LOC) of ITEM in a on successful search or sets LOC=NULL on unsuccessful search.

Step 1:  Set BEGN :=LBD, END:=UBD & MID=INT((BEGN+END)/2).

Step 2:  Repeat Steps 3 and 4 while BEGN<=END and SA[MID]!=ITEM.

Step 3:  If ITEM<SA[MID] then                     (ITEM exist in left sub array)

                Set END:=MID-1.             

                Else                                                   (ITEM exist in right sub array)

                Set BEG:=MID+1.

                END IF.

Step 4:  Set MID:=INT((BEGN+END)/2).

                End while.

Step 5:  If SA[MID]=ITEM then                                                   (Search is successful)

                Set LOC:=MID

                Else

                Set LOC:=NULL.                                                                                (Search is unsuccessful)

                End if

Step 6:  Return LOC.

 

 

Program to search an item using BINARY SEARCH

#include<stdio.h>

#include<conio.h>

#define N 10

void main()

{

                int a[N], itemm, begn, endd, midd;

                int i;

                clrscr();

                printf("enter %d element of an array",N);

                for(i=0;i<N;i++)

                {

                                scanf("%d",&a[i]);

                }

                printf("enter item to be search");

                scanf("%d",&itemm);

                begn=0;

                endd=N-1;

                midd=(begn+endd)/2;

                while(begn<=endd&&a[midd]!=itemm)

                {

                                if(a[midd]>itemm)

                                                endd=midd-1;

                                else

                                                begn=midd+1;

                                midd=(begn+endd)/2;

                }

                if(a[midd]!=itemm)

                {

                                printf("\n item %d not found",itemm);

                }

                else

                {

                                printf("\n item %d found at %d location",itemm,midd+1);

                }

                getch();

}

OUTPUT......

Binary Search

TIME COMPLEXITY OF BINARY SEARCH

·         In this case the list is divided into 2 parts and every time our searching is reduced to one part of the list.

·         Only one comparison is required when list is having N items, then next comparison is when elements become equal to N/2 ,then next when elements become equal to N/4 and so on till the elements reduce to 1.

·         Hence the TIME COMPLEXITY is O(log n) for worst case and O((log n)/2) for average case log n<n for all n>=1.

·         Hence, binary search is faster as compared to linear search.

·         The only disadvantage for binary search is that the list must be sorted to search an element.

ADVANTAGES…

·         Binary search method is useful when the list is large.

·         This method is faster than linear search because as the list is divided into 2 halves, the number of comparisons or searches is less.

·         It takes very less time as compared to linear search(O(log2 n)

        DISADVANTAGES.............

                The only disadvantage of this method is that the array or the list needs to be sorted before hand.

APPLICATION OF SEARCHING.

         Internet

         Search engines

         Online enquiry

         Text pattern

         Finding a record from database

         Spell check utility in Word.