003Binary Search

Problem

给定一个按升序排列的整数数组 nums 和一个整数 target。

请返回 target 在数组中的下标。如果 target 不存在，返回 -1。

你必须写出时间复杂度为 $O(\log n)$ 的算法。

Examples

示例 1

Input:  nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4

解释：9 出现在 nums 中，下标为 4。

示例 2

Input:  nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1

解释：2 不在 nums 中，因此返回 -1。

Constraints

• $1 \leq$ nums.length $\leq 10^4$
• $-10^4 <$ nums[i], target $< 10^4$
• nums 中的所有整数互不相同
• nums 按升序排列