In this Leetcode Search in Rotated Sorted Array Problem Solution There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
Problem solution in Python.
class Solution:
def binary_search(self, array, start, end, target):
""" Binary searches array from start to end, returns index of element
equal to target of there's one, otherwise returns -1.
Time complexity: O(lg(n)). Space complexity: O(1), n is len(array).
"""
while start <= end:
mid = (start + end) // 2
if array[mid] == target:
return mid
elif array[mid] < target:
start = mid + 1
else:
end = mid - 1
return -1 # target wasn't found
```
def search(self, array, target):
""" Returns index of target in sorted rotated array.
Time complexity: O(lg(n)). Space complexity: O(1), n is len(array).
"""
# special case, empty array
if not array:
return -1
# find pivot, i.e. minimum element, using modified binary search
n = len(array)
start, end = 0, n - 1
while start <= end:
mid = (start + end) // 2
if array[mid - 1] > array[mid] < array[(mid + 1) % n]:
break # found it, pivot is at index mid
elif array[mid] <= array[end]:
end = mid - 1
else: # array[mid] >= array[start]
start = mid + 1
# decide in which half of the array to search
if target <= array[-1]: # search in right half
return self.binary_search(array, mid, n - 1, target)
else: # search in left half
return self.binary_search(array, 0, mid - 1, target)
class Solution:
def search(self, array, target):
""" Algorithm does binary search in one pass.
Time complexity: O(lg(n)). Space complexity: O(1), n is len(array).
"""
# special case, empty array
if not array:
return -1
# modified binary search
n = len(array)
start, end = 0, n - 1
while start <= end:
mid = (start + end) // 2
if array[mid] == target: # found the target
return mid
elif array[mid] <= array[end]: # pivot is in the left half
if array[mid] < target <= array[end]: # target is in range (mid, last]
start = mid + 1 # search in right half
else:
end = mid - 1 # search in left half
else: # array[mid] >= array[start], pivot is in the right half
if array[start] <= target < array[mid]: # target is in range [start, mid)
end = mid - 1 # search in left half
else:
start = mid + 1 # search in right half
return -1Problem solution in Java.
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) return -1;
int l = 0, r = nums.length-1;
while(l <= r) {
int m = l+(r-l)/2;
// bug - 1 => filter out the special cases avoiding complex checkings;
if(nums[m] == target) return m;
// bug - 2 => trick to ensure an ordered half;
if(nums[m] < nums[r]) {
if(nums[m]<target && target<=nums[r]) l = m+1;
else r = m-1;
}
else if(nums[m] > nums[r]) {
if(nums[l]<=target && target<nums[m]) r = m-1;
else l = m+1;
}
else return -1; // the last iteration since nums[m] == nums[r] => m == r since no duplicates;
}
return -1;
}Problem solution in C++.
class Solution {
public:
int search(vector<int>& nums, int target) {
if (nums.size() == 0) return -1;
int start=0, end=nums.size()-1;
while (start<end) {
int mid=(start+end)/2;
if (nums[mid] == target) return mid;
// based on which half is sorted, decide the half to target
if (nums[start] <= nums[mid]) { // left half is sorted
if (nums[start] <= target && target < nums[mid]) end=mid-1; // target belongs in left half
else start=mid+1; // otherwise try right half
}
else { // right half is sorted
if (nums[mid] < target && target <= nums[end]) start=mid+1; // target belongs in right half
else end=mid-1; // otheriwse try left half
}
}
return (nums[start] == target) ? start : -1;
}
};Problem solution in C.
int binSearch(int* nums, int l, int r, int target){
int mid;
if (r >= l) {
mid = (l + r + 1) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[l] == target) {
return l;
}
if (nums[r] == target) {
return r;
}
if ((nums[mid] > target) && (nums[r] < nums[mid]) && (nums[r] > target)) {
return binSearch(nums, mid + 1, r , target);
}
if (((nums[l] > nums[mid]) && (nums[mid] < target) && (nums[r] < target)) ||
(nums[mid] > target)) {
return binSearch(nums, l, mid - 1, target);
}
else {
return binSearch(nums, mid + 1, r , target);
}
}
return -1;
}
int search(int* nums, int numsSize, int target){
return binSearch(nums, 0, numsSize-1, target);
}
0 Comments