Untitled
unknown
plain_text
a year ago
1.2 kB
4
Indexable
class Solution { public: int search(vector<int>& nums, int target) { int n = nums.size(); if(nums[0] < nums[n-1]) { return findTarget(nums, n-1, 0, target); } if(target == nums[0]) return 0; int low =0, high = n-1, mid; while(low< high){ mid = low + (high-low)/2; if(nums[mid]>=nums[0]) { low = mid+1; } else { high = mid; } } if(target > nums[0]) { return findTarget(nums, low-1,0 , target); } else { return findTarget(nums,n-1,low,target); } } int findTarget(vector<int>& nums, int high, int low, int target) { int mid; while(low<high) { mid = low + (high-low)/2; if(nums[mid] == target) return mid; if(nums[mid]>= target) { high = mid; } else { low = mid+1; } } if(nums[low] == target) return low; return -1; } };
Editor is loading...
Leave a Comment