[数据结构与算法]Leetcode——35. 搜索插入位置

概述

35. 搜索插入位置

分析

• 题目同样给出一个有序数组，然后也是在其中查找target，只是多了一个查找失败的要求

• 对于一个有序数组的查找问题，很容易想到二分法；

  并且题目也说明数组中的元素不重复，所以不需要考虑重复元素的情况

思路

二分思路？

略

如果查找失败，如何确定插入的位置呢？

• 首先，当我们二分找不到位置，失败时一定有L > R；

  这种情况下，可能是当L==R时，由于L移动引起的，也可能是由于R移动引起的，我们需要分一下L==R的情况：

  • 如果由L向后移动引起，则说明target > num[mid]，插入的位置应该在num[mid]后一个，位置表示为L 或 R + 1 或 mid + 1(此时mid == R)
  • 如果有R向前移动引起，则说明target < num[mid]，插入的位置应该在num[mid]前一个，位置表示为L 或 R + 1 或 mid (此时 mid == L)

• 所以，为了一致性，我们可以选择L 或 R+1都可以

代码

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int L = 0, R = nums.size() - 1;
        while (L <= R) {
            int mid = (R - L) / 2 + L;
            if (target == nums[mid]) return mid;
            else if (target > nums[mid]) L = mid + 1;
            else R = mid - 1;
        }
        // 说明在数组中没有找到target,使用 
        return L;
    }
};

创作挑战赛

新人创作奖励来咯，坚持创作打卡瓜分现金大奖