题目内容

给定一个按升序排列的整数数组 nums，其中不存在重复元素。另有一个整数 target 需要定位。请判断 target 是否出现在数组中：若出现，返回其下标；若未出现，返回为了保持数组升序，target 应插入的位置下标。

求解过程需要满足 $O(\log n)$ 的时间复杂度。

约束条件：

• 数组 nums 的长度 $n$ 满足 $1 \le n \le 10^4$。
• nums 中的每个整数以及 target 的取值均在 $-10^4$ 到 $10^4$ 之间。
• nums 为无重复元素的升序数组。

输入描述

输入包含两个参数：

• nums：一个按升序排列、元素互不相同的整数列表。
• target：需要在 nums 中定位的目标整数。

输出描述

返回一个整数，表示 target 在 nums 中的下标；若 target 不存在于 nums，则返回它按升序插入时应占据的下标。下标从 0 开始。

样例1

输入

1 10
10

输出

0

说明

数组只有一个元素 10，目标值也是 10。目标值出现在下标 0 处，因此返回 0。

样例2

输入

6 0
-5 -3 1 2 4 7

输出

2

说明

有序数组为 -5, -3, 1, 2, 4, 7。目标值 0 不在数组中。按升序插入时，0 应位于 -3 和 1 之间，这个位置的下标是 2，因此返回 2。

样例3

输入

3 -100
-50 0 50

输出

0

说明

有序数组为 -50, 0, 50。目标值 -100 小于数组中的所有元素，所以需要插入到数组最前面。最前面的下标是 0，因此返回 0。

样例4

输入

5 100
-10 0 10 20 30

输出

5

说明

有序数组为 -10, 0, 10, 20, 30。目标值 100 大于数组中的所有元素，所以需要插入到数组末尾。由于数组长度为 5，末尾后一个位置的下标是 5，因此返回 5。