hard20 pts · first answer countssorting-and-searching

Rotated array search with duplicates

Searching a rotated sorted array that allows duplicates, you see a[lo] == a[mid] == a[hi], as in [1, 1, 1, 0, 1, 1]. What can you do, and what does it mean for worst-case time?

A.Pick the left half; it stays O(log n) overallB.Shrink lo and hi by one; worst case is O(n)C.Return "not found" at once; it is O(1)D.Re-sort the array first; it is O(n log n)

Discussion 0

Join free to post in the discussion.

Rotated array search with duplicates

Discussion 0

Related questions