← 返回 bytedance 的题目列表Binary Search
类型：online_judge
Problem: Binary Search
Given a strictly increasing integer array nums and an integer target, return the index of target in nums. Return -1 if target does not exist in the array.
Your algorithm must run in O(log n) time.
Input Format
Line 1: an integer n, the length of the array.
Line 2: n strictly increasing integers representing nums. This line is empty when n = 0.
Line 3: an integer target.
Output Format
Print one integer: the index of target in nums, or -1 if it is absent.
Constraints
0 <= n <= 100,000
-10^9 <= nums[i], target <= 10^9
nums is strictly increasing.
Examples
Input:
6
-1 0 3 5 9 12
9
Output:
4
Input:
6
-1 0 3 5 9 12
2
Output:
-1
Example
Input
6
-1 0 3 5 9 12
9
Output
4