Talk About Network

Google


Register and Login
Nick
Password
Register create new account Sign up is FREE and you can post replies, new topics, bookmark posts and more!
Recover lost password


Programming > C++ Moderated > Binary search q...
Latest [ Topics | Posts ] Archive Post A New Topic Post a Reply
<< Topic < Post Post 1 of 8 Topic 9780 of 9984
Post > Topic >>

Binary search question

by "popeyeray" <popeyeray@[EMAIL PROTECTED] > Jul 11, 2008 at 02:10 PM

2. Consider the array consisting of 7 elements sorted in ascending order.
What is the Maximum number of comparisons that need to be done to find any
given element using:


a. Sequential search (10 points)

b. Binary search (10 points)


Answer below:


a. Since the total number of elements is seven, and the value is unknown I
can only assume that the maximum number of comparisons may be the total
amount of elements, seven (7).


b. The binary search for any given number is what I can't figure out. I
have
attempted to use the following code and formula but am very confused as to
what the answer could be. I can get certain values but when I try for
example the number two as the value to search for it just doesn't work.


       low = 0
       high = N
       while (low < high) {
           mid = (low + high)/2;
           if (A[mid] < value)
               low = mid + 1;
           else
                //can't be high = mid-1: here A[mid] >= value,
                //so high can't be < mid if A[mid] == value
                high = mid;
       }
       if (low < N) and (A[low] == value)
           return low
       else
           return not_found


any help greatly appreciated.


-- 
      [ See http://www.gotw.ca/resources/clcm.htm
for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]
 




 8 Posts in Topic:
Binary search question
"popeyeray" <  2008-07-11 14:10:56 
Re: Binary search question
Oncaphillis <oncaphill  2008-07-11 18:31:22 
Re: Binary search question
partow@[EMAIL PROTECTED]   2008-07-12 03:58:40 
Re: Binary search question
Oncaphillis <oncaphill  2008-07-12 10:38:19 
Re: Binary search question
Mathias Gaunard <loufo  2008-07-12 10:39:02 
Re: Binary search question
brangdon@[EMAIL PROTECTED  2008-07-12 10:36:52 
Re: Binary search question
Francis Glassborow <fr  2008-07-12 10:38:50 
Re: Binary search question
Mathias Gaunard <loufo  2008-07-13 08:10:47 

Post A Reply:
  Go here to Signup

AddThis Feed Button


About - Advertising - Contact - Frequently Asked Questions - Privacy Policy - Terms of Use - Signup

Contact
tan12V112 Sun Sep 7 8:44:08 CDT 2008.