AppliedMultiple choice

Searching a sorted array · Part 2 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 now has duplicates, and you need the index of the first element equal to the target. Which change to the loop is correct and keeps the worst case logarithmic?

AReturn mid as soon as a[mid] == target
BOn a match, record mid and continue with hi = mid - 1
COn a match, step left one element at a time until the value changes, then return that position
DOn a match, continue with lo = mid + 1

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.

Start the 7-day free trial Practise it with Premium

Learn the method

Core techniques: binary search on the answer, two pointers, sliding windows

The array now has duplicates, and you need the index of the first element equal to the target. Which change to the loop is correct and keeps the worst case logarithmic?

More data structures and algorithms questions