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.
The list has length 8.
The integer x is in position 3.
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.
Originally Posted by checkeredshawn
I found that it takes 8 steps to find the number.My list of comparisons is (128 64 96 80 72 68 70 71).
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 :)