# Binary Search Algorithm

• Nov 11th 2006, 09:42 PM
checkeredshawn
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.
• Nov 11th 2006, 10:52 PM
earboth
Quote:

Originally Posted by checkeredshawn
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
• Nov 11th 2006, 10:57 PM
checkeredshawn
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 :)