LeetCode 81 Search in Rotated Sorted Array II

    
        标签：
        
            二分搜索
        
            LeetCode
        
    发布于：2022-03-26 11:07:39
    编辑于：2022-03-26 11:51:10
    浏览量：1029

概述

https://leetcode.com/problems/search-in-rotated-sorted-array-ii/

暴力法

直接暴力遍历。

二分搜索

分类讨论就好了，258 / 279 test cases passed：

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while (l <= r) {
            int m = (r - l) / 2 + l;
            if (nums[m] == target) {
                return true;
            } else if (nums[m] < target) {
                l = m + 1;
            } else { // nums[m] > target
                if (target >= nums[0]) {
                    r = m - 1;
                } else {
                    if (nums[m] >= nums[0]) {
                        l = m + 1;
                    } else {
                        r = m - 1;
                    }
                }
            }
        }
        return false;
    }
};

但是由于相同值的存在上面分类讨论的假设可能并不成立。

https://leetcode.com/problems/search-in-rotated-sorted-array-ii/discuss/28218/My-8ms-C%2B%2B-solution-(o(logn)-on-average-o(n)-worst-case)

哇，是真的恶心，折磨了我好久：

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while (l <= r) {
            int m = (r - l) / 2 + l;
            if (nums[m] == target) {
                return true;
            } else if (nums[l] == nums[m] && nums[r] == nums[m]) {
                l ++;
                m --;
            } else if (nums[l] <= nums[m]) {
                if (nums[m] < target) {
                    l = m + 1;
                } else {
                    if (target >= nums[l]) {
                        r = m - 1;
                    } else {
                        l = m + 1;
                    }
                }
            } else { // nums[l] > nums[m]
                if (nums[m] < target) {
                    if (target >= nums[l]) {
                        r = m - 1;
                    } else {
                        l = m + 1;
                    }
                } else {
                    r = m - 1;
                }
            }
        }
        return false;
    }
};

Links: leetcode-81-search-in-rotated-sorted-array-ii