企业官网建设流程全解析

题目概览

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

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

示例 1:

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

示例 2:

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

示例 3:

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

提示:

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

来源：35. 搜索插入位置 - 力扣（LeetCode）

解题分析

方法：二分查找

从数组中间索引开始找，令该索引为 mid，开始索引为 i，结束索引为 j，则：

1. mid = ( i + j ) / 2
2. nums[ mid ] == target 时，返回
3. nums[ mid ] > target 时，说明在左边，j = mid - 1
4. nums[ mid ] < target 时，说明在右边，i = mid + 1

不断缩小直到 i == j 即可。

时间复杂度：O(logn)
空间复杂度：O(1)

class Solution { public int searchInsert(int[] nums, int target) { int n = nums.length; int i = 0, j = n-1; while(i < j) { int mid = (i + j) / 2; if (nums[mid] == target) { return mid; } if (nums[mid] < target) { i = mid + 1; } else { j = mid - 1; } } return nums[i] < target ? i + 1: i; } }