def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]:
if nums[left] <= target <= nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] <= target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
nums = [4, 5, 6, 7, 0, 1, 2]
target = 0
print(search(nums, target))
Explanation (Python):
The Python solution uses a modified binary search to find the target element in the rotated sorted array.
Initialize two pointers, left and right, representing the left and right boundaries of the search range.
Perform the binary search until left becomes greater than right.
Find the middle element using (left + right) // 2.
If the middle element is equal to the target, return its index.
Check if the left half of the array is sorted (nums[left] <= nums[mid]).
If it is, check if the target falls within the left half (nums[left] <= target <= nums[mid]).
If it does, update the right pointer to mid - 1 to search the left half.
If it does not, update the left pointer to mid + 1 to search the right half.
If the left half is not sorted, it means the right half is sorted.
Check if the target falls within the right half (nums[mid] <= target <= nums[right]).
If it does, update the left pointer to mid + 1 to search the right half.
If it does not, update the right pointer to mid - 1 to search the left half.
If the target is not found, return -1.
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target <= nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (nums[mid] <= target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
public static void main(String[] args) {
int[] nums = {4, 5, 6, 7, 0, 1, 2};
int target = 0;
Solution solution = new Solution();
System.out.println(solution.search(nums, target));
}
}
Explanation (Java):
The Java solution follows the same logic as the Python solution.
Initialize two pointers, left and right, representing the left and right boundaries of the search range.
Perform the binary search until left becomes greater than right.
Find the middle element using left + (right - left) / 2.
If the middle element is equal to the target, return its index.
Check if the left half of the array is sorted (nums[left] <= nums[mid]).
If it is, check if the target falls within the left half (nums[left] <= target && target <= nums[mid]).
If it does, update the right pointer to mid - 1 to search the left half.
If it does not, update the left pointer to mid + 1 to search the right half.
If the left half is not sorted, it means the right half is sorted.
Check if the target falls within the right half (nums[mid] <= target && target <= nums[right]).
If it does, update the left pointer to mid + 1 to search the right half.
If it does not, update the right pointer to mid - 1 to search the left half.
If the target is not found, return -1
#include <iostream>
#include <vector>
using namespace std;
int search(vector& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target <= nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (nums[mid] <= target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
int main() {
vector nums = {4, 5, 6, 7, 0, 1, 2};
int target = 0;
cout << search(nums, target) << endl;
return 0;
}
Explanation (C++):
The C++ solution follows the same logic as the Python and Java solutions.
Initialize two pointers, left and right, representing the left and right boundaries of the search range.
Perform the binary search until left becomes greater than right.
Find the middle element using left + (right - left) / 2.
If the middle element is equal to the target, return its index.
Check if the left half of the array is sorted (nums[left] <= nums[mid]).
If it is, check if the target falls within the left half (nums[left] <= target && target <= nums[mid]).
If it does, update the right pointer to mid - 1 to search the left half.
If it does not, update the left pointer to mid + 1 to search the right half.
If the left half is not sorted, it means the right half is sorted.
Check if the target falls within the right half (nums[mid] <= target && target <= nums[right]).
If it does, update the left pointer to mid + 1 to search the right half.
If it does not, update the right pointer to mid - 1 to search the left half.
If the target is not found, return -1.
I hope this explanation helps! Let me know if you have any further questions.