[数据结构与算法]LeetCode_35_搜索插入位置

题目链接

• https://leetcode.cn/problems/search-insert-position/

解题思路

• 注意题目给定的限制条件：nums为无重复元素的升序排列数组。因此target插入的位置只有三种情况
  • target等于数组中的某一个元素
  • target在数组中两个元素之间，例如2<target=3<4
  • target比数组中所有元素都大
• 法一：遍历数组，如果找到第一个大于等于target的值，那么这个位置就是答案，否则，则说明target比数组中所有元素都大，那么答案就是数组的长度
• 法二：法一属于暴力遍历，时间复杂度为O(n)，因此可以使用二分遍历方法将复杂度降低到O(logn)。这里同样是三种情况
  • 目标值等于数组中某一个元素 return middle;
  • 目标值插入数组中的位置 [left, right]，return right + 1
  • 目标值在数组所有元素之后的情况 [left, right]， 因为是右闭区间，所以 return right + 1

AC代码

//暴力遍历法
class Solution {
    public int searchInsert(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= target)
                return i;
        }
        return nums.length;
    }
}

//二分法
class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (nums[middle] > target) {
                right = middle - 1;
            } else if (nums[middle] < target) {
                left = middle + 1;
            } else
                return middle;
        }
        return right + 1;
    }
}