C++ concise log(n) solution


  • 56
    G
    class Solution {
    public:
      bool search(int A[], int n, int target) {
        int lo =0, hi = n-1;
        int mid = 0;
        while(lo<hi){
              mid=(lo+hi)/2;
              if(A[mid]==target) return true;
              if(A[mid]>A[hi]){
                  if(A[mid]>target && A[lo] <= target) hi = mid;
                  else lo = mid + 1;
              }else if(A[mid] < A[hi]){
                  if(A[mid]<target && A[hi] >= target) lo = mid + 1;
                  else hi = mid;
              }else{
                  hi--;
              }
              
        }
        return A[lo] == target ? true : false;
      }
    };

  • 14
    U

    How about the worst case? O(n)?


  • 4
    R

    The worst case is O(n).


  • 0
    C
    This post is deleted!

  • 1
    C

    Your solution is very nice, this is my Python implementation of it:

    def search(nums, target):
        lo, hi = 0, len(nums)-1
        while lo < hi:
            mid = lo + (hi - lo)/2
            if nums[mid] == target:
                return True
            if nums[mid] > nums[hi]:
                if nums[lo] <= target < nums[mid]:
                    hi = mid
                else:
                    lo = mid + 1
            elif nums[mid] < nums[hi]:
                if nums[mid] < target <= nums[hi]:
                    lo = mid + 1
                else:
                    hi = mid
            else:
                hi -= 1
        return lo < len(nums) and nums[lo] == target

  • 0
    F

    The last code, why we have to do hi-- can not do lo++ ??
    I tried, if do lo++, it will fail, even I change last line to return A[hi]==target ? true:false


  • 2
    G

    That is because we compare the hi with mid each loop and we want to move back and pass by all the duplicated in hi position.


  • 0
    R

    It's true... Actually it's totally no difference with traversal the array directly... Big O are both O(n)


  • 0
    S

    My opinion: if 'hi' is initially set as 'n' rather than 'n-1', then we should change 'hi--' to 'lo++'.
    Am I right or wrong?


  • 6
    C

    The solution is very good and it will be all right if we use the express 'high = mid-1' to replace 'high = mid', besides 'while(low < high)' can be replace by 'while(low <= high), so we just need return false at the end. This is my tips, thank you!


  • 2
    A

    I think, this is not completely correct. For example [3, 1], target = 1, since "hi--" can cause wrong answer.

    Here is my solution.
    http://paste.ubuntu.com/16914208/

    class Solution {
    public:
        int search(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 true;
                } else if (nums[l] <= nums[mid]) {
                    if (nums[l] == nums[mid]) ++l;
                    else if (target >= nums[l] && target < nums[mid]) {
                        r = mid - 1;
                    } else l = mid + 1;
                } else if (nums[mid] <= nums[r]) {
                    if (nums[mid] == nums[r]) --r;
                    else if (target > nums[mid] && target <= nums[r]) {
                        l = mid + 1;
                    } else r = mid - 1;
                } else while (1) ;
            }
            return false;
        }
    };

  • 1
    F

    That's because you are comparing mid with high, not mid with low in "if" statements.
    If num[mid] == num[high], it can be proved that num[high] can be discarded safely, but nothing can say about num[low]
    -- you didn't even check what value num[low] has, how dare you directly discarded it by "low ++".
    Then you may ask, if you use "num[mid] == num[low]" as the condition, can you use low ++?
    The answer is also NO. The reason is you can't know for sure which direction you go by just checking against num[low]
    Why so? This is because this array may be rotated and may be not. For rotated array, checking mid against low or high has same effect,
    but for unrotated array, you should always go to left (minimum is the first one), and checking low would make you go to the other direction.
    Checking high will automatically make you go all the way to the left. In other words, if you use high as the condition, it is same for both
    rotated array and unrotated array, but if you use low, the two cases have opposite conditions.


  • 1
    L

    @fullmetal2000

    bool search(vector<int>& nums, int target) {
        
        int len = nums.size();
        int start = 0, end = len - 1;
        while (start <= end){
            int mid = start + (end - start)/2;
            if (nums[mid] == target) return true;
            if (nums[mid] > nums[start]){
                if (nums[mid] > target && nums[start] <= target) end = mid;
                else start = mid + 1;
            }else if (nums[mid] < nums[start]){
                if (nums[mid] < target && nums[end] >= target) start = mid + 1;
                else end = mid;
            }else start ++;
        }
        return false;
    }

  • 1
    S

    @fentoyal

    @fentoyal said in C++ concise log(n) solution:

    That's because you are comparing mid with high, not mid with low in "if" statements.
    If num[mid] == num[high], it can be proved that num[high] can be discarded safely, but nothing can say about num[low]
    -- you didn't even check what value num[low] has, how dare you directly discarded it by "low ++".
    Then you may ask, if you use "num[mid] == num[low]" as the condition, can you use low ++?
    The answer is also NO. The reason is you can't know for sure which direction you go by just checking against num[low]
    Why so? This is because this array may be rotated and may be not. For rotated array, checking mid against low or high has same effect,
    but for unrotated array, you should always go to left (minimum is the first one), and checking low would make you go to the other direction.
    Checking high will automatically make you go all the way to the left. In other words, if you use high as the condition, it is same for both
    rotated array and unrotated array, but if you use low, the two cases have opposite conditions.

    disagree!
    It is also a way to use low to checking.
    Accept code using low++ ,

        bool search(vector<int>& nums, int target) {
            int l = 0, h = nums.size() - 1;
            while (l < h) {
                int mid = l + (h - l) / 2;
                if (nums[mid] == target) return true;
                if (nums[mid] < nums[l]) {
                    if (nums[mid] < target && nums[h] >= target) l = mid + 1;
                    else h = mid - 1;
                } else if (nums[mid] > nums[l]) {
                    if (nums[mid] > target && nums[l] <= target) h = mid - 1;
                    else l = mid + 1;
                } else {////nums[mid] == nums[l]
                    l++;
                }
            }
            return nums[l] == target;
        }
    

  • 0
    R

    I don't believe there exist an O(log n) algorithm for some extreme cases, if equal items exists. For example:
    1,1,1,1,1,1,1,3,1 how do you find the 3 if you do not exam each number?


  • 0
    A

    Wait, the original post's worst case is O(n) time. O(logn) is the average time.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.