leetcode刷题记录（八十九）——35. 搜索插入位置

（一）问题描述

35. 搜索插入位置 - 力扣（LeetCode）35. 搜索插入位置 - 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 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 <= 104 * -104 <= nums[i] <= 104 * nums 为 无重复元素 的 升序 排列数组 * -104 <= target <= 104https://leetcode.cn/problems/search-insert-position/description/?envType=study-plan-v2&envId=top-100-liked

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

请必须使用时间复杂度为 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 <= 104
• -104 <= nums[i] <= 104
• nums 为 无重复元素 的 升序 排列数组
• -104 <= target <= 104

（二）解决思路

        这道题和704.二分查找的区别只有target不存在与nums中的情况，当target不在nums中是，这道题就变成了找数组中第一个大于target的元素。

        这里用ans来记录，起始值为nums的长度，便于处理边缘情况。在取左区间时记录ans，而右区间时不记录，这是为了统一当target不在nums中时应该取区间的左侧值还是右侧值。这是因为在取左区间且左区间仅包含两个元素时，target的插入位置应该取右侧值，应该等到left和right相等，即区间只剩下一个元素时再取左侧值（此时左侧值和右侧值相等）；在取右区间且右区间仅包含两个元素时，target插入位置应该取左侧值。

class Solution {public int searchInsert(int[] nums, int target) {//每次比较的区间包含左右端点int left = 0, right = nums.length-1,ans=nums.length;while(left<=right){int mid=(left+right)/2;if(target==nums[mid]){return mid;}else if(target<nums[mid]){ans=mid;right=mid-1;}else{left=mid+1;}}return ans;}
}