Blind Halving Search

Medium

An intern wrote a search that works "like binary search" but never checked whether the list was sorted. To look for a number target, the function does this: 1. While the sequence is not empty, pick a **random** element of it as the pivot. 2. If the pivot equals target, the search succeeds. 3. If the pivot is less than target, remove the pivot and everything to its left. 4. If the pivot is greater than target, remove the pivot and everything to its right. 5. If the sequence runs out, the search fails. You are given an array values of distinct integers, not necessarily sorted. Count how many of its values this function finds **no matter which** pivots it picks.

Example 1

values=[2, 1, 3, 5, 4] → 1

Only 3 is larger than everything to its left and smaller than everything to its right, so whatever pivot comes up, 3 is never thrown away. For instance, 1 can be lost: if 2 is drawn first while looking for 1, the 2 and everything to its right go, and 1 goes with them.

Example 2

values=[-4, 0, 9] → 3

The list is already sorted, so the search is reliable for all three values.

Example 3

values=[6, 5, 4] → 0

Every value can get lost. When looking for 6, the 4 may be drawn first: it is smaller than the target, so it is dropped along with everything to its left, 6 included.

Constraints

1 ≤ len(values) ≤ 10⁵
-10⁵ ≤ values[i] ≤ 10⁵
All numbers in values are distinct

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Binary Search