[LeetCode 笔记] 35. Search Insert Position

前言

　　这题标準运用了二分搜寻法，演算法通常需要使用二分思想，即每次能够排除一半的範围，快速的找出阵列中所要求的元素位置，这样时间複杂度可达 O(log n)，另外也可以使用一层迴圈找出元素位置，但时间複杂度会下修到O(n)，这里有 JAVA 和 Python 的写法。

题目

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.

给定一个已排序过有不同整数和目标值的阵列，如果有这个目标值就回传这个索引 ，如果没有这个值，就回传按顺序插入后的索引。
你必须写出一个算法，为 O(log n) 的时间複杂度。

题目连结：https://leetcode.com/problems/search-insert-position/

题目限制

1 <= nums.length <= 104
104 <= nums[i] <= 104
nums contains distinct values sorted in ascending order.
104 <= target <= 104

範例

Input: nums = [1,3,5,6], target = 5Output: 2

Input: nums = [1,3,5,6], target = 2Output: 1

Input: nums = [1,3,5,6], target = 7Output: 4

思路&笔记

主要是运用二分搜寻法来快速的找到值的位置，原理是每次循环都会将搜索範围缩小一半。
如果 target 比中间值大，那么搜索範围将在中间值的右侧。
如果 target 比中间值小，那么搜索範围将在中间值的左侧。

middle = start + ( end - start ) / 2 可取得中间值找出目标值在中间值的左侧还是右侧搜索範围越来越小，直到最后回传起点位置就是答案

[注意点] 之所以要用上述中间值的写法会比较安全，因如果 start 和 end 趋近于最大数时，两者相加起来的合可能会造成整数溢位

[备注] 回传 start 原因是，在二分搜寻法中，每次都会将搜索範围缩小一半。而搜寻範围最小的时候，如果目标值不在该範围内，那么搜寻将停止。而此时，start 和 end 分别会指向搜寻範围的左右两端，此时 start 恰好会指向 target 应该插入的位置，因此最后返回 start 即可。

JAVA 实现

class Solution {    public int searchInsert(int[] nums, int target) {        int start = 0; // 起点位置int end = nums.length-1; // 终点位置// 进入迴圈while (start <= end ){// 创建中间值int middle = start + ( end - start ) / 2;if (target == nums[middle]) { // 目标值 = 阵列中间值return middle; // 找到答案，回传中间值索引}else if (target < nums[middle]) { // 目标值 < 阵列中间值 end = middle-1; // 重新定义终点，下次回圈找到新的终点就好 (因为目标值一定比自己小，要不包含 middle 自己)}else { // 目标值 > 阵列中间值 start = middle+1; // 重新定义起点，下次回圈从新的起点开始就好 (因为目标值一定比自己大，要不包含 middle 自己)}}        return start;    }}

JAVA 其他实现

class Solution {    public int searchInsert(int[] nums, int target) {        int len = nums.length; // 阵列长度                for (int i = 0; i < len; i++) {            if (nums[i] >= target) { // 大于等于目标值                return i; // 就回传当前索引            }        }        return len;    }}

Python 实现

使用了和 Java 一样的逻辑执行，换成 Python 的写法。

class Solution:    def searchInsert(self, nums: List[int], target: int) -> int:start = 0 # 起点        end = len(nums)-1 # 终点        while start <= end:            # 设定中间值            middle = start + (end-start)//2            # 判断 target 是否等于 middle            if target == nums[middle]:                return middle            # 判断 target 是否大于            elif target > nums[middle]:                start = middle+1            # 判断 target 是否小于            else :                end = middle-1        return start

成绩

(新手上路，如有错误请友善告知，感谢)

Blog
https://chris81051.github.io/2023/05/17/LeetCode-35-Search-Insert-Position-Java-Python/
有分享技术文章、科技新闻、日常生活，欢迎一起讨论