来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-insert-position/
题目描述
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
题目分析
根据题目要求本题『请必须使用时间复杂度为 O(log n) 的算法』,可想到二分查找。
代码实现
public class SouSuoChaRu_35 {
public static void main(String[] args) {
SouSuoChaRu_35 erFenChaZhao_704 = new SouSuoChaRu_35();
int[] nums = {1, 3, 5, 6};
int target = 7;
erFenChaZhao_704.search(nums, target);
}
public int search(int[] nums, int target) {
int leftIndex = 0;
int rightIndex = nums.length - 1;
int result = nums.length;
while (leftIndex <= rightIndex) {
int midIndex = (rightIndex + leftIndex) / 2;
if (nums[midIndex] >= target) {
rightIndex = midIndex - 1;
result = midIndex;
System.out.println(result);
} else {
leftIndex = midIndex + 1;
}
}
System.out.println("result:" + result);
return result;
}
}
复杂度
- 时间复杂度：O(logn)，其中 n 是定版本的数量。
- 空间复杂度：O(1)，只需要常数的空间保存变量。
好了，今天就到这里，感谢各位看官到这里，不如点个关注吧！
