Question

Consider the following list: 5,12,25,32,38,46,58,62,85,90,97,105,110 Using the binary search as described in this chapter, how many comparisons are required to find whether the following items are in the list? Show the values of first, last, and middle and the number of comparisons after each iteration of the loop. a. 32 b. 20 c. 105 d. 60

Short answer

32 requires 4 comparisons; 20 requires 4; 105 requires 3; 60 requires 3.

Step-by-step solution

Understand Binary Search

Binary search is an efficient algorithm for finding a target value within a sorted array. The search operates by dividing the array in half and comparing the middle element with the target value. If they match, the search stops. If the target is less than the middle element, the search continues on the lower half. Otherwise, it continues on the upper half. This process repeats until the target is found or the subarray size becomes zero.

Search for 32

1. Initialize: first = 0, last = 12 2. First iteration: Calculate middle = (0 + 12) / 2 = 6, check list[6] = 58. Since 32 < 58, update last = 5. 3. Second iteration: Calculate middle = (0 + 5) / 2 = 2, check list[2] = 25. Since 32 > 25, update first = 3. 4. Third iteration: Calculate middle = (3 + 5) / 2 = 4, check list[4] = 38. Since 32 < 38, update last = 3. 5. Fourth iteration: Calculate middle = (3 + 3) / 2 = 3, check list[3] = 32. Found the number. Total comparisons: 4.

Search for 20

1. Initialize: first = 0, last = 12 2. First iteration: Calculate middle = (0 + 12) / 2 = 6, check list[6] = 58. Since 20 < 58, update last = 5. 3. Second iteration: Calculate middle = (0 + 5) / 2 = 2, check list[2] = 25. Since 20 < 25, update last = 1. 4. Third iteration: Calculate middle = (0 + 1) / 2 = 0, check list[0] = 5. Since 20 > 5, update first = 1. 5. Fourth iteration: Calculate middle = (1 + 1) / 2 = 1, check list[1] = 12. Since 20 > 12, update first = 2. Item not found. Total comparisons: 4.

Search for 105

1. Initialize: first = 0, last = 12 2. First iteration: Calculate middle = (0 + 12) / 2 = 6, check list[6] = 58. Since 105 > 58, update first = 7. 3. Second iteration: Calculate middle = (7 + 12) / 2 = 9, check list[9] = 90. Since 105 > 90, update first = 10. 4. Third iteration: Calculate middle = (10 + 12) / 2 = 11, check list[11] = 105. Found the number. Total comparisons: 3.

Search for 60

1. Initialize: first = 0, last = 12 2. First iteration: Calculate middle = (0 + 12) / 2 = 6, check list[6] = 58. Since 60 > 58, update first = 7. 3. Second iteration: Calculate middle = (7 + 12) / 2 = 9, check list[9] = 90. Since 60 < 90, update last = 8. 4. Third iteration: Calculate middle = (7 + 8) / 2 = 7, check list[7] = 62. Since 60 < 62, update last = 6. Item not found. Total comparisons: 3.

Key concepts

Algorithm Efficiency

Binary search is celebrated for its efficiency. It operates on a sorted array, trimming the search space in half with every step. This is unlike a linear search, which might require checking each element one by one until a match is found.

Binary search uses a logarithmic time complexity, specifically \(O(\log n)\), where \(n\) is the number of elements in the array. This means that the number of steps it takes to find a value grows very slowly even if you double or triple the number of items in your list.

Imagine you have a book with a hundred pages. A linear search would involve flipping through every single page if the title you need is on the last page. However, with a binary search, you'd split the book first to see if the middle page contains the title, cutting down your search effort significantly. This process is repeated, making it notably faster than checking every page in sequence.

Sorted Array

A sorted array is essential for binary search. Without sorting, the algorithm would not be able to reliably decide whether to continue searching the left side or the right side after each comparison.

In the exercise example, the list is sorted in ascending order: 5, 12, 25, 32, 38, 46, 58, 62, 85, 90, 97, 105, 110. This ordering allows the binary search algorithm to quickly narrow down the possible location of a search target.

Sorting can be performed using a variety of techniques such as quicksort or mergesort, both of which are generally quite efficient. The initial sorting step is crucial because it sets a structured base for the binary search, enabling the algorithm to eliminate half of the array swiftly with each iteration.

Iteration Steps

Iteration steps during a binary search follow a systematic process. The algorithm computes the middle of the current search range and compares it to the target value. Depending on whether the element at the middle is higher, lower, or equal to the searched value, it adjusts the search range.

For instance, searching for 32 commenced with the initial range covering the entire array (from index 0 to 12). The middle is calculated, a decision is made on whether to move left or right, and this narrows the search.

The number of iteration steps determines the efficiency of your search. With each iteration, the search zone halves, quickly trimming down the possibilities. Usually, \( \log_2(n)\) iterations are required, making it a swift process even in large datasets. The iterative checking is a hallmark of the binary search method.

Comparisons in Search

In binary search, comparisons are a core component of the activity. Each step in the search process is driven by a comparison between the middle element of the current search segment and the target value.

Each comparison helps decide whether the remaining elements to search are on the left or right of the middle point. For example, to find the number 105, the algorithm compares the middle value with 105 and finds it needs to look further to the right after each step.

The number of comparisons made provides a benchmark for the efficiency of the search. In the exercise, 4 comparisons were needed for some searches, while others required only 3. A successful or unsuccessful search is directly linked to these comparisons, with a minimal number helping quickly conclude the search process.

Through repeated comparisons, binary search exemplifies how structured choices on where to search next allow for a fast and effective reduction of possibilities.