Optimized Randomized Binary Search

This problem explores a modified binary search algorithm. In the traditional binary search on a sorted, strictly increasing array, the middle index is deterministically selected. However, in this problem, the programmer bh1234666 randomized the choice of the middle index in each iteration. Specifically, at every iteration a random value w is chosen in {0, 1} and the middle index is computed as:

\( mid=\frac{l+r+w}{2} \)

• For w=0: mid = \(\lfloor\frac{l+r}{2}\rfloor\) and the update is as follows:
  • If num[mid] < x, then l = mid + 1
  • Otherwise, r = mid
• For w=1: mid = \(\lceil\frac{l+r}{2}\rceil\) and the update is:
  • If num[mid] - 1 < x, then l = mid
  • Otherwise, r = mid - 1

The process repeats until l == r and a counter cnt is incremented at each iteration. Given a sorted sequence (of length n) and a target number x (which is guaranteed to exist in the array), your task is to determine the minimum possible number of iterations (i.e. the minimal final value of cnt) that this algorithm can take if the choices of w are optimized.

Note: Although the role of w may seem confusing, you can analyze the update rules on the index interval. For example, if the current search interval has length 8 (indices [0,7]), regardless of the random choices, the next search interval will be either [0,3] or [4,7]. Similarly, for an interval of length 7, the branch decision may vary based on w. You may simulate the procedure in terms of indices.

inputFormat

The first line contains an integer n indicating the number of elements in the array.

The second line contains n space‐separated integers representing the sorted, strictly increasing array.

The third line contains an integer x which is guaranteed to be present in the array.

outputFormat

Output a single integer which is the minimum possible number of iterations (the minimal value of cnt) needed to find x using the described randomized binary search algorithm.

sample

3
1 3 5
1

1