Linear Verses Binary Search We have a phone book consisting

Linear Verses Binary Search

We have a phone book consisting of 1024 entries. The names in the phone book are ordered alphabetically, each name associated with a phone number. You desire to locate a name in the phone book and you are considering two search techniques: i linear search and ii binary search. For the linear search, what is the average number of comparisons required to locate the phone number? For a binary search how many comparisons are necessary?

For a binary search, how is the number of cxomparisons related to the number of elements n in the data base?

Can you exhibit a recursive algorithm for each search technique, for instance using pseudo code?

Solution

For linear search to search or locate from 1024 phone numbers we need n/2=1024/2=512 average number of comparisons required

for binary only one search is need when it is best case and when it is average number of comparisons required two comparisions need.

If the list is stored as an ordered array, then binary search is almost always more efficient than linear search as with n > 8, say, unless there is some reason to suppose that most searches will be for the small elements near the start of the sorted list.

the searchh process is as first take first element as:first

                                          and mid element as :mid

                                          and end element as:end

   later search:search element<=mid or not

      if it ok then first take first element as:first

                                          and mid element as :calculate

                                          and end element as:mid

later search:search element<=mid is not

      i then first take first element as:mid

                                          and mid element as :calculate

                                          and end element as:end

pseudo code for recursive algorithm for linear search technique:

            LINEAR_SEARCH(A.v)

           for i<--1 to length(A)

           do if A[i]=v

          then return i

           return NIL

   pseudo code for recursive algorithm for binary search technique:

       if(l>r) then return (-1)

       m=([l+r]/2);

      if(A[m]<v)

    then return (bsearch(a,m+1,r,v))

   else return (bsearch(a,l,m-1,v)).