In the Leetcode Search in Rotated Sorted Array II problem solution, There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).
Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]. For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].
Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.
You must decrease the overall operation steps as much as possible.
Example 1:
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Example 2:
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
Constraints:
- 1 <= nums.length <= 5000
- -104 <= nums[i] <= 104
- nums is guaranteed to be rotated at some pivot.
- -104 <= target <= 104
Solution in C Progamming
bool search(int* nums, int numsSize, int target){
int left = 0, right = numsSize - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return true;
}
if (nums[mid] > nums[left]) {
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else if (nums[mid] < nums[left]) {
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
} else {
left++;
}
}
return false;
}
int solution(int argc, char *argv[]) {
int nums[] = {2,5,6,0,0,1,2};
int target = 0;
printf("%d\n", search(nums, sizeof(nums)/sizeof(int), target));
return 0;
}Solution in C++ Programming
class Solution {
public:
bool search(vector<int>& nums, int target) {
int n=nums.size();
if(n==0) return false;
int low=0,high=n-1;
if(nums[n-1]>nums[0]) // this is just an extra condition to check if the array has been rotated or not
{
int idx=lower_bound(nums.begin(),nums.end(),target)-nums.begin();
if(idx==n) return false;
if(nums[idx]!=target) return false;
return true;
}
while(low<=high)
{
int mid=low+(high-low)/2;
if(nums[mid]==target) return true;
else if(nums[mid]>nums[high])
{
if(nums[mid]>target)
{
if(nums[low]<=target) high=mid-1;
else low=mid+1;
}
else
{
low=mid+1;
}
}
else if(nums[mid]<nums[high])
{
if(nums[mid]>target) high=mid-1;
else
{
if(nums[high]>=target) low=mid+1;
else high=mid-1;
}
}
else high--;
}
return false;
}
};Solution in Java Programming
class Solution {
public boolean search(int[] nums, int target) {
int start = 0, end = nums.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) return true;
else if (nums[mid] > nums[start]) {
if (target >= nums[start] && target < nums[mid]) end = mid - 1;
else start = mid + 1;
}
else if (nums[mid] < nums[start]){
if (target <= nums[end] && target > nums[mid]) start = mid + 1;
else end = mid - 1;
} else {
start += 1;
}
}
return false;
}
} Solution in Python Programming
class Solution:
def search(self, nums, target):
def binSearch(left, right):
if left > right:
return False
mid = (left + right) // 2
if nums[mid] == target:
return True
elif nums[left] < nums[mid] and (target < nums[left] or target > nums[mid]):
return binSearch(mid+1, right)
elif nums[mid] < nums[right] and (target < nums[mid] or target > nums[right]):
return binSearch(left, mid-1)
else:
return binSearch(left, mid-1) or binSearch(mid+1, right)
return binSearch(0, len(nums)-1)Solution in C# Programming
public class Solution {
public bool Search(int[] nums, int target) {
int len = nums.Length;
int lo = 0;
int hi = len - 1;
while(lo + 1 <= hi && nums[lo + 1] == nums[lo]) lo++;
while(hi - 1 >= lo && nums[hi - 1] == nums[hi]) hi--;
while(lo < hi)
{
int mid = (lo + hi) / 2;
if(nums[mid] == target || nums[lo] == target || nums[hi] == target)
{
return true;
}else if(nums[mid] > nums[lo])
{
if(target > nums[lo] && target < nums[mid])
{
hi = mid - 1;
while(hi - 1 >=0 && nums[hi - 1] == nums[hi]) hi--;
}else
{
lo = mid + 1;
while(lo + 1 < len && nums[lo + 1] == nums[lo]) lo++;
}
}else
{
if(target > nums[mid] && target < nums[hi])
{
lo = mid + 1;
while(lo + 1 < len && nums[lo + 1] == nums[lo]) lo++;
}else
{
hi = mid - 1;
while(hi - 1 >=0 && nums[hi - 1] == nums[hi]) hi--;
}
}
}
return target == nums[lo];
}
}Also read,