文章目录
- 搜索插入位置 Search Insert Position
- 思路
- Tag
搜索插入位置 Search Insert Position
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
假设数组中无重复元素。
[1,4,5,7] , 5
: 2
1 < = n u m s . l e n g t h < = 1 0 4 − 1 0 4 < = n u m s [ i ] < = 1 0 4 n u m s 为无重复元素的升序排列数组 − 1 0 4 < = t a r g e t < = 1 0 4 1 <= nums.length <= 10^4\\ -10^4 <= nums[i] <= 10^4\\ nums 为 无重复元素 的 升序 排列数组\\ -10^4 <= target <= 10^4 1<=nums.length<=104−104<=nums[i]<=104nums为无重复元素的升序排列数组−104<=target<=104
思路
最原始的方法就是遍历时间复杂度 O ( N ) O(N) O(N)
有2个可能
-
查到数据，返回索引
-
查不到数据，返回应该被插入的位置。
待插入的数据为x，而且数组是有序的，所以需要在一个有序数组中找第一个大于等于X的下标,所以可以通过二分查找来定位。
public int searchInsert(int[] nums, int target) {int l = 0 ; int r = nums.length-1;while (l<=r){int mid = (l+r)>>1;if(nums[mid]==target){return mid;}else if(nums[mid]>target){r =mid -1;}else{l = mid +1;}}return l;}
Tag
math binary search
