Search in Rotated Sorted Arrays
Search in Rotated Sorted Arrays
No.33 Find a value in an ascending array without duplicates and return its index.
int search(vector<int>& nums, int target) {
int start=0;
int end=nums.size()-1;
while(start<=end) {
int mid=(start+end)>>1;
if (nums[mid]==target) return mid;
if (nums[mid]>=nums[start]) {
if (target<nums[mid] && target>=nums[start]) {
end=mid-1;
} else {
start=mid+1;
}
} else {
if (target>nums[mid] && target<=nums[end]) {
start=mid+1;
} else {
end=mid-1;
}
}
}
return -1;
}No.81 Find a value in an ascending array with duplicates and return its index.
bool search(vector<int>& nums, int target) {
int start=0;
int end=nums.size()-1;
while(start<=end) {
// Remove duplicate elements
while(start<end && nums[start]==nums[start+1]) ++start;
while(end>start && nums[end]==nums[end-1]) --end;
int mid=(start+end)>>1;
if (nums[mid]==target) return true;
if (nums[mid]>=nums[start]) {
if (target<nums[mid] && target>=nums[start])
end=mid-1;
else
start=mid+1;
} else {
if (target>nums[mid] && target<=nums[end])
start=mid+1;
else
end=mid-1;
}
}
return false;
}Jian Zhi Offer: Find the smallest element?
Always go toward the opposite direction of the increasing interval in binary search, until the front and back indices become adjacent. The element pointed to by the back index is the smallest element.
Special case: When the elements pointed to by the front, middle, and back are all equal, we cannot perform binary partitioning. In this case, linear search is needed.
#search