Compute how many steps binary search would take to find an item in arrays of various sizes.

You mean that there is a maximum of 8 steps if the element exists in the array,

but 9 steps if the element does not exist?

Hello Melody!

YES!

\(\begin{array}{|lrcll|} \hline & \text{We search number 1:} & & \text{set } \{1,\dots,193 \}\\\\ (1) & 1 > \lfloor \frac{1+193}{2} \rfloor = 97 & no & \text{new set } \{1,\dots,97 \}\\ (2) & 1 > \lfloor \frac{1+97}{2} \rfloor = 49 & no & \text{new set } \{1,\dots,49 \}\\ (3) & 1 > \lfloor \frac{1+49}{2} \rfloor = 25 & no & \text{new set } \{1,\dots,25 \}\\ (4) & 1 > \lfloor \frac{1+25}{2} \rfloor = 13 & no & \text{new set } \{1,\dots,13 \}\\ (5) & 1 > \lfloor \frac{1+13}{2} \rfloor = 7 & no & \text{new set } \{1,\dots,7 \}\\ (6) & 1 > \lfloor \frac{1+7}{2} \rfloor = 4 & no & \text{new set } \{1,\dots,4 \}\\ (7) & 1 > \lfloor \frac{1+4}{2} \rfloor = 2 & no & \text{new set } \{1,2 \}\\ (8) & 1 > \lfloor \frac{1+2}{2} \rfloor = 1 & no & \text{we have found number 1 in the last set}\\ \hline \end{array} \\ \begin{array}{|lrcll|} \hline & \text{We search number 1.5:} & & \text{set } \{1,\dots,193 \}\\\\ (1) & 1.5 > \lfloor \frac{1+193}{2} \rfloor = 97 & no & \text{new set } \{1,\dots,97 \}\\ (2) & 1.5 > \lfloor \frac{1+97}{2} \rfloor = 49 & no & \text{new set } \{1,\dots,49 \}\\ (3) & 1.5 > \lfloor \frac{1+49}{2} \rfloor = 25 & no & \text{new set } \{1,\dots,25 \}\\ (4) & 1.5 > \lfloor \frac{1+25}{2} \rfloor = 13 & no & \text{new set } \{1,\dots,13 \}\\ (5) & 1.5 > \lfloor \frac{1+13}{2} \rfloor = 7 & no & \text{new set } \{1,\dots,7 \}\\ (6) & 1.5 > \lfloor \frac{1+7}{2} \rfloor = 4 & no & \text{new set } \{1,\dots,4 \}\\ (7) & 1.5 > \lfloor \frac{1+4}{2} \rfloor = 2 & no & \text{new set } \{1,2 \}\\ (8) & 1.5 > \lfloor \frac{1+2}{2} \rfloor = 1 & yes & \text{new set } \{ 2 \}\\ (9) & 1.5 = 2 & no & \text{we have not found number 1.5 in the last set}\\ \hline \hline \end{array}\)

Compute how many steps binary search would take to find an item in arrays of various sizes.

Let n = size of the array

Let c = comparisons in the worse case

\(\begin{array}{|rcll|} \hline c &=& 1 + \log_2(n) \qquad & | \qquad \log_2(n) = \dfrac{ \ln(n) }{\ln(2)} \\ c &=& 1 + \dfrac{ \ln(n) }{\ln(2)} \\\\ n &=& 193\\ c &=& 1 + \dfrac{ \ln(193) }{\ln(2)} \\\\ c &=& 1 + \dfrac{ 5.26269018890 }{0.69314718056} \\\\ c &=& 1 + 7.59245703727 \\ c &=& 8.59245703727 \\ c &\approx& 9 \\ \hline \end{array} \)

No more than 9.

Thanks Heureka but can you explain to me why you have to add the 1 ?

Hi EMP,

I did one of these for you the other day :)

Just assume that it is the very last one that is the one you are looking for and see how lon it would take.

193 in the array.

Let the first on be in postion 0 and the last one be in position 193

1.      (0+193)/2 =  96     rounded down

2.      (0+96)/2   =  48

3.      (0+48)/2   =  24

4.      (0+24)/2   = 12

5.      (0+12)/2=    6

6.      6/2=3

7.      3/2=1

8.       1/2=0

That is 8

So I think that 9 will do it.

Thanks Heureka :)

Thank you! :)