← 返回 snapchat 的题目列表Binary Search with Boundary Conditions
类型：online_judge
Implement binary search: given a non-decreasing array nums and an integer x, return the first occurrence index (lowest index) of x. Return -1 if x does not exist.
Requirements:
Time complexity O(log n).
Constraints:
1 <= n <= 2*10^5
-10^9 <= nums[i], x <= 10^9
nums may contain duplicates.
I/O format (ACM style):
Input: line1 n, line2 n sorted integers, line3 integer x
Output: one integer, the first index of x (0-based), or -1
Example:
Input:
6
1 2 2 2 3 4
2
Output:
1
Example
Input
6
1 2 2 2 3 4
2
Output
1