A Common-Sense Guide to Data Structures and Algorithms in JavaScript, Volume 1

Chapter 2

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

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 ...