#2176. 搜索插入位置

搜索插入位置

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

格式

输入

第一行 :一个整数n 第二行:n个整数 第三行:目标值target

输出

target若存在,输出target下标,否则输出target按顺序插入的位置

样例1

4
1 3 5 6 
5
2

样例2

4
1 3 5 6
2
1

样例3

4
1 3 5 6
7
4

提示:

  • 1 <= nums.length <= 10<sup>4</sup>
  • -10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>
  • nums无重复元素 ​升序 ​排列数组
  • -10<sup>4</sup> <= target <= 10<sup>4</sup>