LeetCode 35. Search Insert Position

LeetCode 35. Search Insert Position

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.

解法一 Binary Search

思路

要在有序数组里找到插入目标的位置，首先想到就是利用二分查找，将 target 和数组里的数进行比较。

代码

class Solution {
    public int searchInsert(int[] nums, int target) {
        // Handle edge case
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int lo = 0;
        int hi = nums.length - 1;

        while (lo + 1 < hi) {
            int mid = (hi - lo) / 2 + lo;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                hi = mid;
            } else {
                lo = mid;
            }
        }

        // 由于退出循环时 相邻的两个 hi, lo 索引未与 target 进行比较，所以还要进行一次比较
        if (nums[hi] < target) {
            return hi + 1;
        } else if (nums[lo] >= target) {
            return lo;
        }
        return hi;
    }
}

复杂度分析

• 时间复杂度
  • O(nlogn)
• 空间复杂度
  • O(1)

本作品采用《CC 协议》，转载必须注明作者和本文链接