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

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

示例 1:

1
2
输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

1
2
输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

1
2
输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为 无重复元素 的 升序 排列数组
-104 <= target <= 104

思路1

暴力解体

遍历数组，当前下标值>=target返回坐标，没有返回最大长度

思路2

二分算法去解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public int searchInsert(int[] nums, int target) {
       return findTarget(nums,  0,nums.length -1, target);
   }

   int findTarget(int[] nums, int start, int end, int target){

       // 不存在数值的时候,开始比结束要大
       if (start > end){
           return start;
       }

       // 中间数下标 = 开始下标 + 未比较个数/2(中间值)
       int mid = start + (end - start) / 2;
       // 中间数值
       int midNum = nums[mid];
       // 中间数== 目标值返回坐标
       if (midNum == target){
           return mid;
       }

       
       if (midNum > target){
           // 中间数值 小于 目标就要取数组左边全部数据
           // (mid - 1) 是因为取左边数据,需要要把中间数的坐标给删除掉
           return findTarget(nums, start, mid - 1 , target);
       } else {
           // 中间数值 小于 目标就要取数组右边全部数据
           // (mid + 1) 是因为取右边数据,需要要把中间数的坐标给删除掉
           return findTarget(nums, mid + 1 , end, target);
       }

   }

作者：力扣 (LeetCode)
链接：https://leetcode.cn/leetbook/read/array-and-string/cxqdh/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。