If we use the binary search algorithm to search for 31 from the following list,

Question

If we use the binary search algorithm to search for 31
from the following list,
1, 7, 8, 11, 15, 19, 20, 23, 31, 90,
how would we actually do it? The lecture slides
showed the following pseudocode

binarySearch(key,a,first,last)
set found to false
DOWHILE (first <= last) AND (NOT found)
set middle = [ (first + last)/2 ]
IF a(middle) = key THEN
set found to true
ELSE
IF key > a(middle) THEN
first = middle + 1
ELSE
last = middle 1
ENDIF
ENDIF
ENDDO

for the algorithm, explain the role of each statement
there, and why it is so.

Explanation / Answer

please rate - thanks

hope this is what your looking for. If not message me

To do a binary search you start by comparing the key (what your looking for) to the middle number in the list.

if the key matches, you've found what your looking for. If it is larger, you repeat the operation with the top half of the list, if smaller repeat with the bottom of the list. You are finished either when you find the key or exhaust the list. Thelist will be exhausted when the smaller index of the list, for the search, actually becomes larger then the larger index into the list

binarySearch(key,a,first,last)         parameters are, key-what looking for, a-array looking in, first-first index of array (usually 0 or 1 depending on language being used), last- last index of array(usually size of array, or size of array-1 again based on language)
set found to false                       found false indicates key hasn't been found
DOWHILE (first <= last) AND (NOT found)     do until list is exhausted or ky is found
       set middle = [ (first + last)/2 ]            get the index of the middle element of the mportion of the array you are interested in
       IF a(middle) = key THEN             is the middle element the one with the key
              set found to true                if yes, set found true so you will exit the loop-your done
       ELSE                                            if not
               IF key > a(middle) THEN       if the key is greater then the middle element, you are interested in the top portion of the array, so the last element stays the same, but the first element now becomes the element whos index is 1 greater then that of the middle element
                       first = middle + 1
               ELSE                              if the key is less then the middle element, you are interested in the bottom portion of the array, so the first element stays the same, but the last element now becomes the element whos index is 1 less then that of the middle element
                        last = middle 1
               ENDIF
      ENDIF
ENDDO

example

1, 7, 8, 11, 15, 19, 20, 23, 31, 90,

looking for 31   first=0, last =9

middle element    = element 4 which is 15

31> 15 so now set first to 5, last stays at 9

middle element is element (5+9)/2=element 7 which has a 23

31>23 so set first element to 8, last starys at 9

middle element is (8+9)/2 =element 8 which has a 31

31=31 set found true, and exit the loop

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.