← 返回 meta 的题目列表Binary Search on a sorted array (boundary/corner cases)
类型：online_judge
Problem
Given an integer array nums sorted in non-decreasing order (may contain duplicates) and an integer target, find the index of target.
If target exists, return any valid index.
Otherwise, return -1.
Requirement
O(log n) time.
I/O Format
Input:
Line 1: integer n
Line 2: n integers (sorted array)
Line 3: integer target
Output:
One line: the index or -1
Constraints
0 <= n <= 2 * 10^5
-10^9 <= nums[i] <= 10^9
Array is sorted (non-decreasing)
Example
Input:
5
1 2 4 4 7
4
Output:
2
(Any of 2 or 3 is acceptable.)
Example
Input
5
1 2 4 4 7
4
Output
2