Find pivot in rotated sorted array in C++
Introduction:
In C++ programming, when dealing with arrays that are sorted in ascending or descending order, it's often straightforward to perform operations like searching or inserting elements. In this tutorial, we'll explore an efficient approach to finding the Pivot in a rotated sorted array using C++, making use of binary search techniques.
Understanding Rotated Sorted Arrays:
Imagine an array arr initially sorted in ascending order: [1, 2, 3, 4, 5]. If we rotate it by two positions, we get [4, 5, 1, 2, 3]. The element at index 0 (originally 4) becomes the "pivot" because it is the first element larger than its immediate predecessor.
Here are the key properties of rotated sorted arrays:
- The array can be viewed as a combination of two sorted sub-arrays: [pivot + 1, ..., n-1] and [0, ..., Pivot].
- The pivot element itself might not be the minimum or maximum value in the array.
Approaches to Solve:
- Linear Search: A naive approach is used to perform a linear search through the array, checking for the pivot element. However, this method has a time complexity of O(n), where n is the size of the array. While simple, it's inefficient for large datasets.
- Binary Search: A more efficient approach is to utilize binary search. This algorithm has a time complexity of O(log n), making it much faster for large arrays. Binary search involves repeatedly dividing the array into halves and deciding which half to continue searching based on certain conditions.
Finding the Pivot using Binary Search:
Leveraging binary search, we can efficiently locate the Pivot in an array. Here's the algorithm:
1. Initialization: Set two pointers, left and right, to the beginning and end of the array.
2. Binary Search Loop:
- While the left is less than or equal to the right:
- Calculate the middle index mid using (left + right) / 2.
- Analyze the ordering of elements around mid:
- If arr[mid] > arr[right], the Pivot lies on the right side. Update left to mid + 1.
- If arr[mid] <= arr[right], the Pivot could either be at mid or on the left side. Update right to mid (inclusive).
3. Pivot Found: When the loop terminates, the left will point to the index just after the pivot element. Return left - 1 as the pivot index.
Example:
Let us take an example to illustrate how to find pivot in rotated sorted array in C++.
#include <iostream>
#include <vector>
using namespace std;
// Function to find the pivot in a rotated sorted array
int findPivot(const vector<int>& nums) {
int low = 0;
int high = nums.size() - 1;
while (low < high) {
int mid = low + (high - low) / 2;
// If mid is greater than the next element, mid+1 is the pivot
if (nums[mid] > nums[mid + 1]) {
return mid + 1;
}
// If mid is less than the previous element, mid is the pivot
if (nums[mid] < nums[mid - 1]) {
return mid;
}
// If the left half is sorted, pivot is in the right half
if (nums[low] < nums[mid]) {
low = mid + 1;
} else { // If the right half is sorted, pivot is in the left half
high = mid - 1;
}
}
// If no pivot is found, the array is not rotated, return 0
return 0;
}
int main() {
// Example usage
vector<int> nums = {4, 5, 6, 7, 0, 1, 2};
int pivotIndex = findPivot(nums);
cout << "Pivot is at index: " << pivotIndex << endl;
return 0;
}
Output:
Pivot is at index: 4
Explanation:
- The findPivot function takes the array arr and its size n as input.
- The left and right pointers mark the search boundaries.
- The while loop iterates until the pivot is bracketed between left and right.
- The mid-calculation ensures that we don't overflow when adding left and right.
- The condition arr[mid] > arr[right] helps identify if the pivot lies on the right side.
- If arr[mid] is not greater than arr[right], either mid itself is the pivot, or it lies before mid.
- After the loop ends, the left will point to the index just after the pivot. We return left - 1 as the actual pivot index.
- The main function demonstrates usage, printing the pivot index or indicating if the array isn't rotated.
Conclusion:
In conclusion, finding the pivot in a rotated sorted array efficiently is crucial for various algorithms. By employing binary search, we can achieve this task with a time complexity of O(log n), making it suitable for large datasets. The provided C++ implementation demonstrates how to find the pivot effectively. This approach simplifies the process and ensures optimal performance when dealing with rotated sorted arrays.