two binary search O(log N) 6ms C++ solution


  • -1
    Y

    FIrst while loop look for index h such that a[h] > a[h+1]. If there's no rotation, both l and h will be set to the last index last. Then compare target with the first element a[0] to decide whether to look for target in a[0] to a[h] or in a[h+1] to a[last].

    class Solution {
    public:
      int search(vector<int>& a, int target) {
        int last = a.size()-1, l = 0, h = last, k = 0;
        while (l < h) {
          k = (l+h+1) >> 1;
          if (a[k] < a[l])
            h = k-1;
          else
            l = k;
        }
        if (target >= a[0])
          l = 0;
        else {
          l = h+1;
          h = last;
        }
        while (l <= h) {
          k = l+h >> 1;
          if (target < a[k])
            h = k-1;
          else if (target > a[k])
            l = k+1;
          else
            return k;
        }
        return -1;
      }
    };
    

Log in to reply
 

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