Question

Use the binary search algorithm to decide whether 35 is in the following list: \(3,6,7,9,12,14,18,21,22,31,43\) What numbers will be compared with 35 ?

Short answer

The numbers compared with 35 are 14, 22, 31, and 43.

Step-by-step solution

Initial List and Middle Element

The list we have is already sorted: \(3, 6, 7, 9, 12, 14, 18, 21, 22, 31, 43\). In binary search, we start by comparing the target number 35 with the middle element of the list. Since there are 11 elements, the middle element is at position \(\lceil \frac{11}{2} \rceil = 6 \), which is 14.

Compare 35 with 14

We compare 35 with the middle element, 14. Since 35 is greater than 14, we eliminate the left half of the list (including 14) and focus only on the elements to the right. The new sublist is \(18, 21, 22, 31, 43\).

Find New Middle Element

The new sublist \(18, 21, 22, 31, 43\) has 5 elements. The middle element is at position \(\lceil \frac{5}{2} \rceil = 3\), which is 22.

Compare 35 with 22

35 is greater than 22, so we discard the left portion up to 22. Our subsequent sublist is \(31, 43\).

Final Middle Element

The sublist \(31, 43\) has 2 elements. The middle element \(\lceil \frac{2}{2} \rceil = 1\), is 31.

Compare 35 with 31

Since 35 is greater than 31, we discard 31 as well, leaving us with \(43\).

Compare 35 with 43

Now, we are left with 43, the only element. We compare 35 with 43. Since 35 is less than 43 and no more elements are left to check, 35 is not present in the list.

Key concepts

Binary Search Process

Binary search is a method used to efficiently find a target value within a sorted array. It is more efficient than a linear search, as it systematically reduces the problem size by half at each step. To employ binary search on an array, start by finding the middle element. This element will divide the array into two halves.

• If the middle element is equal to the target value, the search is successful, and the position is returned.
• If the target value is less than the middle element, the search continues on the left subarray.
• Otherwise, the target value is greater, and the search continues on the right subarray.

This process repeats with each successive subarray until the target is found or the array is exhausted. The efficiency of binary search comes from significantly narrowing the search range with each comparison, making it ideal for large or sorted data sets.

Comparison Steps

During the binary search process, comparisons determine the direction of the search. With each comparison, the size of the search area is reduced, based on whether the target value is higher or lower than the middle element. Here’s how it worked in our example: Initially, the middle element was 14. Since 35 is greater than 14, search continued to the right sublist.

• First Sublist: [3, 6, 7, 9, 12, 14, 18, 21, 22, 31, 43]
• Middle Element: 14
• Comparison with 35: Target is greater, move right.

The next middle element was 22. Again, because 35 surpasses 22, the left part was discarded.

• Second Sublist: [18, 21, 22, 31, 43]
• Middle Element: 22
• Comparison with 35: Target is greater, continue right.

Finally, 35 was compared with 31.

• Third Sublist: [31, 43]
• Middle Element: 31
• Comparison with 35: Target is greater, only 43 remains.

35 was checked against 43, confirming it wasn't present in the list. This sequence of comparisons illustrates why organized steps are essential in binary search.

Search Efficiency

Binary search is renowned for its speed and efficiency compared to other search algorithms, especially in large datasets. The primary advantage is its logarithmic reduction of search space, allowing the algorithm to discard half of the remaining elements with each comparison. When assessing efficiency:

• Binary search requires that the list is sorted in advance. This may require additional pre-processing but pays off with rapid search times.
• It has a time complexity of \( O(\log{n}) \) where \( n \) is the number of elements in the array. This means, as the size of the list increases, the search time increases at a logarithmic rate.
• The search is optimal for situations where quick lookups are crucial and preprocessing is manageable or already done.

Think of binary search as a sifting mechanism that efficiently rules out irrelevant sections of data. Its ability to quickly home in on the necessary subarray speeds up the computation significantly, making it an essential tool in computer science and high-volume databases.