Results 1 to 3 of 3

Math Help - Binary Search Algorithm

  1. #1
    Newbie
    Joined
    Nov 2006
    Posts
    4

    Binary Search Algorithm

    Hello, the question is:

    For each of these questions, you are given the size of an ordered list of integers. In each case, tell how many steps the binary search algorithm takes to find an integer in the given position or to decide that the integer described is not present in the list. Count one step for each time the algorithm would examine an array element A[i]. Enter your answer as a list inside parentheses.
    Example:
    The list has length 8.
    The integer x is in position 3.
    Steps: 5
    Comparison list: (4 2 3)


    The one that I am stuck on is:

    The list has length 128.
    The integer x is in position 71.

    I found that it takes 7 steps to find the number, but my list of comparisons, which I thought would be (128 96 80 72 68 70 71) is wrong.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    earboth's Avatar
    Joined
    Jan 2006
    From
    Germany
    Posts
    5,829
    Thanks
    123
    Quote Originally Posted by checkeredshawn View Post
    Hello, ...
    The list has length 128.
    The integer x is in position 71.
    I found that it takes 7 steps to find the number, but my list of comparisons, which I thought would be (128 96 80 72 68 70 71) is wrong.
    Hello,

    I found that it takes 8 steps to find the number.My list of comparisons is (128 64 96 80 72 68 70 71).

    EB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2006
    Posts
    4
    Thank you for the insight, and actually, the homework server that we use for this class has a check button and it said that there were 7 steps, so after I realized from your post that it would have to check 64, the comparison list came out to be (64 96 80 72 68 70 71). Thanks again
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: February 20th 2010, 11:58 PM
  2. Search Algorithm, Numerical Methods
    Posted in the Advanced Applied Math Forum
    Replies: 2
    Last Post: September 6th 2009, 07:41 AM
  3. Inequalities and log base 2 search algorithm problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 29th 2007, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum