Search in Rotated Sorted Array II

Description

Follow up for Search in Rotated Sorted Array:

What if duplicates are allowed?

• Binary search is no longer a proper choice

Would this affect the run-time complexity? How and why?

• Yes, the average run-time complexity will be O(n). Although the best case is still O(logn), we cannot predict the situation of dup in the array .
  The dup will affect every action of search. We have to move the index to the region of non-dup

Write a function to determine if a given target is in the array.

Example
Given [1, 1, 0, 1, 1, 1] and target = 0, return true.
Given [1, 1, 1, 1, 1, 1] and target = 0, return false.

Link

Lintcode_ladder

Method

1. Access everyone with one pass
2. Binary search has not stable run-time

Example

1. 1

class Solution {
    /** 
     * param A : an integer ratated sorted array and duplicates are allowed
     * param target :  an integer to be search
     * return : a boolean 
     */
public:
    bool search(vector<int> &nums, int target) {
        // write your code here
        if (nums.empty()) {
            return false;
        }
        bool result = false;
        for (int i = 0; i < nums.size(); ++i) {
            if (target == nums[i]) {
                result = true;
                break;
            }
        }
        return result;
    }
};
// no sign to move: [1 1 1 1 1 1 1 1]
// so use o(n) to search

Similar problems

x

Tags

x