LeetCode.035.Search Insert Position 搜索插入位置

题目描述

035 Search Insert Position
https://leetcode-cn.com/problems/search-insert-position/
https://leetcode.com/problems/search-insert-position/description/

Given a sorted array 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 may assume no duplicates in the array.

Example 1:

Input: [1,3,5,6], 5
Output: 2

Example 2:

Input: [1,3,5,6], 2
Output: 1

Example 3:

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

Example 4:

Input: [1,3,5,6], 0
Output: 0

---

解题过程

经典的二分搜索，没啥说的，如果要搜索的值不再数组中，最后肯定以high+1==low结束。

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

SolutionV2018

private static class SolutionV2018 {
    public int searchInsert(int[] nums, int target) {
        if (nums.length == 0) {
            return 0;
        }
        int low = 0;
        int high = nums.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (target == nums[mid]) {
                return mid;
            } else if (target > nums[mid]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return high + 1;//最后high+1肯定等于low
    }
}

SolutionV2020

2020 年写这个题，注意到了二分搜索计算 mid 时可能溢出的问题。

private static class SolutionV202007 {
    public int searchInsert(int[] nums, int target) {
        if (null == nums || nums.length < 1) {
            return 0;
        }
        int left = 0, 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;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_035_SearchInsertPosition.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_035_SearchInsertPosition.java

---