Find the Hidden Number

Problem Statement

Find the Hidden Number There is a hidden rotated sorted array of n distinct integers. Your task is to find the index of a target number within it. The array was originally sorted in strictly increasing order and then rotated at some unknown pivot. For example: Original array: [1, 2, 3, 4, 5, 6, 7] Rotated array: [4, 5, 6, 7, 1, 2, 3] You are allowed to interact with the hidden array by querying the value at any index. Your goal is to find the position of the target value x . You can ask at most 128 queries. Input Format: Your program will receive a single line with two integers n and x (1 ≤ n ≤ 10 6 , 1 ≤ x ≤ 10 9 ), where x is guaranteed to exist in the array. The next n lines each contain one integer — the elements of the hidden array. Output Format: Output a single line in the format ! i , where i is the index such that A[i] = x . Note that indexing is zero-based. Note: In the second test case, the hidden array is: [ 3, 4, 5, 1, 2 ] The first query is made at index