A search method for sorted data that compares the target with the middle element and halves the search range each time. It finds a value among n items in at most ⌊log₂ n⌋ + 1 comparisons, so its complexity is O(log n). The data must be sorted.
Japanese name: 二分探索
Binary search appears in 7 practice questions across 3 topics, including Data Structures and Algorithms, A/D and D/A conversion, Software Development and Project Management.
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).
Answer: A. 10
Each comparison roughly halves the search range, and 2¹⁰ = 1024 ≥ 1000, so the range is used up after at most 10 comparisons (⌊log₂ 1000⌋ + 1 = 10). The complexity is O(log n), and even 1,000,000 values need at most 20 comparisons. 32 corresponds to √1000 ≈ 31.6, and 500 is close to the average for a linear search (about n/2). Keep in mind, though, that binary search needs sorted data, and sorting itself costs O(n log n).
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.
Which is a prerequisite for using binary search, which comp…Keep in mind, though, that binary search needs sorted data, and sorting itself costs O(n log n).
A binary search is performed on 1,000 distinct values sorte…Testing one commit at a time from the oldest would take 999 tests in the worst case and about 500 on average, so binary search makes a big difference.
After a firmware version known to work correctly there are …A successive-approximation (SAR) ADC compares the input with an internal DAC output starting from the most significant bit, settling one bit per step like a binary search.
Which correctly describes the operation of a successive-app…A SAR ADC performs a binary search, comparing the input with its internal DAC from the MSB down and settling one bit per comparison, so N bits basically need N comparisons.
How many comparisons does an N-bit successive-approximation…As an Amazon Associate I earn from qualifying purchases.
Array Git Comparator Microcontroller (MCU) Oversampling Successive-approximation ADC Binary heap Binary search tree Breadth-first search Depth-first search