leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0033.cpp (912B)

      1 class Solution {
      2     int binary_search(const vector<int> &nums, int target, int low, int high) {
      3         while (low <= high) {
      4             int mid = low + (high - low) / 2;
      5             if (nums[mid] == target)
      6                 return mid;
      7             else if (nums[mid] > target)
      8                 high = mid - 1;
      9             else
     10                 low = mid + 1;
     11         }
     12         return -1;
     13     }
     14 
     15   public:
     16     int search(vector<int> &nums, int target) {
     17         int pivot = -1;
     18         for (int i = 0; i < nums.size() - 1; i++) {
     19             if (nums[i] > nums[i + 1]) {
     20                 pivot = i;
     21                 break;
     22             }
     23         }
     24         if (pivot == -1) return binary_search(nums, target, 0, nums.size() - 1);
     25         if (nums[0] <= target)
     26             return binary_search(nums, target, 0, pivot);
     27         else
     28             return binary_search(nums, target, pivot + 1, nums.size() - 1);
     29     }
     30 };