712111. Search in Rotated Array 2
Search in Rotated Array 2
Summary
The problem involves searching for an element in a rotated array. A rotated array is an array that has been shifted to the right by a certain number of positions, and then the first element of the rotated array becomes the last element of the original array. The goal is to write a function that takes the rotated array and the target element as input, and returns the index of the target element in the array.
Detailed Explanation
The problem can be solved using binary search with some modifications to account for the rotation. Here's a step-by-step breakdown of the solution:
-
First, we need to find the pivot point of the rotated array. The pivot point is the point where the array was rotated. We can do this by comparing the first and last elements of the array. If they are in order (i.e., the first element is less than or equal to the last element), then the array has not been rotated, and we can perform a standard binary search.
-
If the array has been rotated, then we need to find the pivot point. We do this by comparing the middle element of the array with the first element. If the middle element is greater than the first element, then the pivot point is on the left side of the middle element. Otherwise, it's on the right side.
-
Once we have found the pivot point, we can perform a binary search on the appropriate half of the array (either the left or right half).
Here's some sample code in Python to illustrate this:
def search_rotated_array(arr, target):
if arr[0] <= arr[-1]:
return binary_search(arr, target)
mid = len(arr) // 2
if arr[mid] >= arr[0]:
left_half = arr[:mid]
right_half = arr[mid:]
else:
left_half = arr[mid:]
right_half = arr[:mid]
if target in left_half:
return binary_search(left_half, target)
else:
return binary_search(right_half, target)
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1 # not found
Optimized Solutions
Java
public int search(int[] nums, int target) {
if (nums[0] <= nums[nums.length - 1]) {
return binarySearch(nums, target);
}
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else 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; // not found
}
public int binarySearch(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1; // not found
}