Searching and Sorting

Binary search compares the target with the middle element and discards half of the remaining range. It needs two things to be correct and \(O(\log n)\):

• Sorted data. Discarding a half is justified only when the elements are in order. On unsorted input the search can throw away the half that holds the target, so binary search does not work for A or B.
• Constant-time access to the middle. A linked list must be walked node by node to reach its middle, costing \(\frac{n}{2} + \frac{n}{4} + \cdots = O(n)\) in total, so D is not \(O(\log n)\) even though the list is sorted.

Only the sorted array (C) meets both conditions.

Answer: C

Each swap in insertion sort exchanges two adjacent elements that are out of order, removing exactly one inversion. So the number of swaps equals the number of inversions.

Without \(x\), the only inversion is the pair (15, 13), so \(x\) must add exactly one more:

• \(x = 10\): only 11, placed before it, is larger. Total 2.
• \(x = 12\): no element is out of order with it. Total 1.
• \(x = 14\): only 13, placed after it, is smaller. Total 2.
• \(x = 16\): both 15 and 13, placed after it, are smaller. Total 3.

Answer: A, C

The array is already sorted. In the first partition the pivot is 100 and every other element is smaller, so they all already sit on the left side and the pivot is already in its final place. Each later call looks the same: on 60 70 80 90 the pivot 90 is the largest, then 80, then 70.

A Lomuto-style partition would only ever swap an element with itself here, because its two indices are always equal, and such a step moves nothing and can be skipped. No element ever has to change place, so the minimum number of swaps is 0.

Answer: 0

Binary search compares the target with the middle element. Either it matches, or the search continues in just one of the two parts left after removing the middle. With \(n\) elements the larger part has \(\lfloor n/2 \rfloor\) elements, so in the worst case one comparison is followed by a search of size \(\lfloor n/2 \rfloor\):

\[F(n) = F(\lfloor n/2 \rfloor) + 1, \quad F(1) = 1,\]

which solves to \(F(n) = \lfloor \log_{2} n \rfloor + 1\).

Option B searches both halves, C forgets the comparison just made (so \(F\) would never grow), and D discards only one element per step, which describes linear search.

Answer: A

Trace two passes of each algorithm on [4, 3, 2, 1, 5]:

• Bubble sort: pass 1 carries 4 to its place, giving [3, 2, 1, 4, 5]; pass 2 carries 3, giving [2, 1, 3, 4, 5]. Not yet sorted.
• Insertion sort: pass 1 inserts 3, giving [3, 4, 2, 1, 5]; pass 2 inserts 2, giving [2, 3, 4, 1, 5]. Not yet sorted.
• Selection sort: pass 1 swaps the minimum 1 into the first position, giving [1, 3, 2, 4, 5]; pass 2 swaps 2 into the second position, giving [1, 2, 3, 4, 5]. Sorted.

Only selection sort is done, because its two swaps happen to fix every misplaced element; bubble sort and insertion sort each need a third pass.

Answer: B