leetcode-search-in-rotated-sorted-array

发表于   |   分类于 ，   |  

题目大意

https://leetcode.com/problems/search-insert-position/

给定一个排好序的数字，找出值target元素所在的位置，如果没有找到，返回应该插入的位置。

[1,3,5,6], 5 → 2

[1,3,5,6], 2 → 1

[1,3,5,6], 7 → 4

[1,3,5,6], 0 → 0

解题思路

二分查找。

  • 写法1:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    int searchInsert(vector<int>& nums, int target) {
            int low = 0, high = nums.size();
            while(low < high) {
                int mid = (low + high) / 2;
                if(nums[mid] < target) {
                    low = mid + 1;
                } else {
                    high = mid;
                }
            }
            return low;
    }

    [low,high]为可能的区间，每次循环以后更新low和high值仍保证此性质，并且不会进入死循环。

  • 写法2:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    int searchInsert(vector<int>& nums, int target) {
        if(target < nums[0]) {
            return 0;
        }
        int size = nums.size();
        if(target > nums[size - 1]) {
            return size;
        }
        int L = -1;
        int R = nums.size() - 1;
        int mid;
        while(L + 1 < R) {
            mid = (L + R) / 2;
            if(nums[mid] >= target) {
                R = mid;
            } else {
                L = mid;
            }
        }
        return R ;
    }

    （L,R]为可能区间,每次循环以后更新low和high值仍保证此性质(注意循环开始前一句排除掉了一些边界情况，才能保证不进入死循环或者说保证循环的正确性)，并且不会进入死循环。