LeetCode_二分搜索_简单_35.搜索插入位置

1.题目

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

示例 1： 输入: [1,3,5,6], 5 输出: 2

示例 2： 输入: [1,3,5,6], 2 输出: 1

示例 3： 输入: [1,3,5,6], 7 输出: 4

示例 4： 输入: [1,3,5,6], 0 输出: 0

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/search-insert-position

2.思路

当目标元素 target 不存在数组 nums 中时，搜索左侧边界的⼆分搜索的返回值可以从以下三个方面进行解释： ① 返回值是 nums 中大于等于 target 的最小元素索引； ② 返回值是 target 应该插入在 nums 中的索引位置； ③ 返回值是 nums 中小于 target 的元素个数；

比如在有序数组 nums = [1,3,5,6] 中搜索 target = 2，搜索左边界的二分算法会返回 1，带入上面的解释，都是对的。故以上三种解释都是等价的，可以根据具体题目场景灵活运用，显然这里是第⼆种。

3.代码实现（Java）

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left