Leecode 35 ----- 搜索插入位置
题目描述
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
思路
二分查找
时间复杂度：O(log n)在这里插入代码片
左侧下标 left = 0；
右侧下标 right = 0；
判断：while (left <= right)
- 中间下标 mid = (left + right) / 2
- 比较nums[mid] 和 target 的大小
- 相等，返回 mid 下标，return mid
- nums[mid] < target，left = mid + 1
- nums[mid] > target，right = mid - 1
return left；
实现
/**
* Author: lisiyu
* Created: 2020/1/20
*/
// 二分查找
public class SearchInsert35 {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
if (nums.length == 0) {
return 0;
}
if (nums[nums.length - 1] < target) {
return nums.length;
}
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
}