FoundationNumeric answer
Searching a sorted array · Part 1 of 3
A sorted array of integers is searched with classic binary search: keep a range [lo, hi], compare the target with the middle element, and discard the half that cannot contain it.
The array holds 1,000 distinct values and the target may be missing. In the worst case, how many array elements does the search compare with the target before it stops?
Answer with a number. Fractions, powers and expressions like 23/6 or C(52,5) are read correctly in practice.
The worked solution is in Premium
The answer, the full working and the one idea to take away – for this and all 1,322 questions in the bank. Answer it in practice and your working is marked, with a known mistake named when you make one.
More data structures and algorithms questions
- How many comparisons does a binary search need, in the worst case, over a…Foundation
- How many non-empty contiguous subarrays does an array of length ten have?Foundation
- What is the largest sum of a contiguous subarray of [−2,1,−3,4,−1,2,1,−5,4]?Applied
- What is the length of the longest substring of "abcabcbb" with no repeated characters?Applied
- Parcels weighing 1,2,…,10 must ship in order within 5 days, each day’s load…Advanced
- Any comparison sort must, in the worst case, make at least ⌈log₂n!⌉ comparisons.Advanced