Chapter 2

These are the solutions to the exercises found in the section .

1. Linear search on this array would take four steps. We start at the beginning of the array and check each element from left to right. Because the 8 is the fourth number, we’ll find it in four steps.

2. Binary search would take just one step in this case. We start the binary search at the middlemost element, and the 8 just happens to be the middlemost element!

3. To solve this, we need to count how many times we halve 100,000 until we get down to 1. If we keep dividing 100,000 by 2, we see that it takes us sixteen times until we get down to about 1.53. If we halve this a seventeenth time, we get roughly 0.76, which is already below 1. This suggests that in a worst-case scenario, it takes either sixteen or seventeen steps to perform binary search on 100,000 elements. If your answer is either sixteen or seventeen, it means you understand this concept well. Nice job!

   In practice, binary search takes sixteen steps. We can see this if we (tediously) walk through each step.

   Let’s start with 100,000 elements. When dealing with an even number of elements, there isn’t an exact item in the center. Instead, there are two central elements, and we arbitrarily search one of them. By searching this element, we’ve essentially taken it out of the picture, leaving behind 50,000 elements on one side of it and 49,999 on the other side. In the worst-case scenario, the value we’re searching for is among the 50,000 elements.

   Let’s perform a few more searches. Our second search leaves us with 25,000 elements. Our third search leaves 12,500 elements remaining. Our fourth search whittles down the elements to 6,250. The fifth search leaves us with 3,125 elements.

   Now, this is the first time we’re encountering an odd number of elements. Here, there’s a single central element, and when we search it, each side will have 1,562 elements. Therefore, when doing the math for our next search, we can subtract 1 from 3,125 (since we’ve removed the central element from the picture) and divide 3,124 by 2. This, as we noted, gives us 1,562.

   When we continue this pattern, it emerges that it takes sixteen steps to halve 100,000 until we find the value we’re searching for.