Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Search in a rotated sorted array two methods
Method-I //Searcch in a rotated sorted array class Solution { public: int search(vector<int>& nums, int target) { int s=0; int e=nums.size()-1; int mid; while(s<=e) { mid=(s+e)/2; if(nums[mid]==target) { return mid; } else if(nums[mid]>=nums[s]) { if(target>=nums[s] and target<=nums[mid]) { e=mid-1; } else { s=mid+1; } } else { if(target>=nums[mid] and target<=nums[e]) { s=mid+1; } else { e=mid-1; } } } return -1; } }; Method II 1. finding the index of the lowest element and then decide which side to move 2. then applying binary search to find the target element class Solution { public: int search(vector<int>& nums, int target) { int s=0; int e=nums.size()-1; int n=nums.size(); int mid; while(s<e) { mid=(s+e)/2; if(nums[mid]>nums[e]) { s=mid+1; } else { e=mid; } } int pivot=s; s=0; e=n-1; if(target>=nums[pivot] and target<=nums[e]) { s=pivot; } else { e=pivot; } while(s<=e) { mid=(s+e)/2; if(nums[mid]==target) return mid; else if(target>nums[mid]) { s=mid+1; } else { e=mid-1; } } return -1; } };
run
|
edit
|
history
|
help
0
tes
pattern
break.cpp
C++ Solar eclipse program(Shoushi integrated) 1644 - 1785 from Ideone( Date: August 14, 2014 )
Expected types
Bin Tree playground
List add v2
is_num_palindrom
MapTel2
amma2