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

逃离我推掉我的手 2023-10-06 18:07 60阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 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 <= right) {
        
                int mid = left + (right - left) / 2;
                if (nums[mid] == target) {
        
                    return mid;
                } else if (nums[mid] < target) {
        
                    left = mid + 1;
                } else {
        
                    right = mid - 1;
                }
            }
            return left;
        }
    }