English
Menu

Data Structures and Algorithms

Which is a prerequisite for using binary search, which compares the target with the middle element and halves the search range each time?

  1. AThe number of data items must be a power of two
  2. BThe data must be sorted by key
  3. CThe data must not contain duplicate values
Show answer and explanation

Answer: B. The data must be sorted by key

Binary search uses the result of comparing the target with the middle element to decide whether the target lies in the first or second half, and halves the range. That conclusion holds only because the data is sorted, so binary search cannot be used on an unsorted array. The number of items does not need to be a power of two; choosing the middle as (low + high) ÷ 2 rounded down works for any size. Duplicates are also fine: one of the matching values is found (finding the first occurrence takes a small extra step).

  • A. Choosing the middle by rounding down works for any number of items.
  • B. Correct. Because the data is sorted, a comparison with the middle element tells you which half to keep.
  • C. Search still works with duplicates; one of the matching values is found.
Practice this topic Back to topic

Related calculators

Binary search tree and heap visualizerDraw the binary search tree or heap built by inserting values in order, and show the preorder, inorder and postorder traversals, the search path and the heap's array layoutTime complexity (Big-O) comparison toolCompare the number of steps and the time for O(log n), O(n), O(n log n), O(n²), O(2ⁿ) and more as the data grows, and estimate the running time for a different data size

Books on Data Structures and Algorithms Ad

As an Amazon Associate I earn from qualifying purchases.

More Data Structures and Algorithms questions

  1. A binary search is performed on 1,000 distinct values sorted in ascending order. If one comparison tells you whether the values are equal, smaller or larger, what is the maximum number of comparisons, counting both successful and unsuccessful searches?
  2. A binary search looks for 38 in the ascending array a[0] to a[9] = 3, 8, 12, 17, 23, 31, 38, 45, 52, 60. The search range starts with lo = 0 and hi = 9, and the middle position is (lo + hi) ÷ 2 rounded down. Which lists, in order, the elements compared with 38?
  3. The array 5, 3, 8, 1, 4 is sorted in ascending order with bubble sort. What is the array after one pass, in which neighboring elements are compared from the front to the end and swapped whenever the left one is larger?
  4. The array 29, 10, 14, 37, 13 is sorted in ascending order with selection sort, which finds the minimum of the unsorted part and swaps it with the first element of the unsorted part. What is the array after this step has been done twice?
  5. An array of 10 elements is sorted in ascending order with insertion sort. Each element from the second one on is taken out and compared with the elements to its left, starting with its left neighbor, until an element less than or equal to it is found or the front is reached. How many comparisons are made when the array is already in ascending order, and when it is in descending order?