Problem Statement
Given an integer array nums, sorted in ascending order (with distinct values) and a target value k. The array is rotated at some pivot point that is unknown. Find the index at which k is present and if k is not present return -1.
Examples
Example 1:
Input: nums = [4, 5, 6, 7, 0, 1, 2], k = 0
Output: 4
Explanation: Obviously the target k = 0 is present at index 4 in the array.Example 2:
Input: nums = [4, 5, 6, 7, 0, 1, 2], k = 3
Output: -1
Explanation: The target k = 3 is not present in the array so return -1.Different Approaches
1️⃣ Linear Search
Intuition:
The naive approach to solve this problem is by traversing the array linearly and returning the index at which we find the target element. In case we don't find the target element in the array we return -1.
Approach:
- Traverse the array & for each element in the array, check if it is equal to the target. If a match is found, return the index of the matching element.
- If the entire array is traversed and no matching element is found, return -1 to indicate that the target is not present in the array.
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to search for the target element in the array
int search(vector<int>& nums, int target) {
// Get the size of the array
int n = nums.size();
// Loop through the array to find the target element
for (int i = 0; i < n; i++) {
// Check if the current element is the target
if (nums[i] == target)
// Return the index if the target is found
return i;
}
// Return -1 if the target is not found
return -1;
}
};
int main() {
vector<int> nums = {4, 5, 6, 7, 0, 1, 2};
int target = 0;
// Create an instance of the Solution class
Solution sol;
// Function call to search for the target element
int result = sol.search(nums, target);
if (result == -1)
cout << "Target is not present.\n";
else
cout << "The index is: " << result << "\n";
return 0;
}
Complexity Analysis:
- Time Complexity:
O(N),N= size of the given array. Since we have to iterate through the entire array to check if the target is present in the array. - Space Complexity:
O(1), as we have not used any extra data structures. This makes space complexity, even in the worst case,O(1).
2️⃣ Binary Search
Intuition:
The optimal approach would be by dividing the array in halves and implement binary search. The most important thing to note here is that, at any middle point, one side of the array will still be sorted. Use this logic & by figuring out which half is sorted, decide which half to keep searching in, making the search efficient even in a rotated array.
1. Despite being rotated, at least one half of the array will always be sorted
2. By identifying the sorted half, we can determine whether the target lies within it or not.Approach:
- Start with two pointers:
lowat the beginning andhighat the end of the array & calculate the midpoint (mid). Ifnums[mid]is the target, returnmid. - Determine which half of the array is sorted.
- If the left half is sorted and the target is within this range, search in the left half.
- Otherwise, search in the right half, if it is sorted and the target is within this range.
- Continue this process until the pointers
lowandhighcross. If the target is not found, return-1.
Dry Run:
Initialization:
+-----+-----+-----+-----+-----+-----+-----+
nums = | 4 | 5 | 6 | 7 | 8 | 1 | 2 |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
^ ^
| |
left right
left = 0
right = 6
Target = 1left 0, right = 6
left = 0
right = 6
Target = 1
mid = left + (right - left) / 2
= 0 + (6 - 0) / 2
= 3
+-----+-----+-----+-----+-----+-----+-----+
nums = | 4 | 5 | 6 | 7 | 8 | 1 | 2 |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
^ ^ ^
| | |
left mid right
Is nums[mid] == Target
7 == 1
False
Check which part is sorted left or right
If nums[left] <= nums[mid]
4 <= 7
True
Means Left part is sorted.
Check if our Target is within the range
of left part
Does nums[left] <= Target && Target <= nums[mid]
4 <= 1 && 1 <= 7
False
It means our Target would be in right part, so go right.
Set left = mid + 1
= 3 + 1
= 4
// The else part when the right part is sorted.left = 4, right = 6
left = 4
right = 6
Target = 1
mid = left + (right - left) / 2
= 4 + (6 - 4) / 2
= 4 + 2/2
= 4 + 1
= 5
+-----+-----+-----+-----+-----+-----+-----+
nums = | 4 | 5 | 6 | 7 | 8 | 1 | 2 |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
^ ^ ^
| | |
left mid right
Is nums[mid] == Target
nums[5] == Target
1 == 1
True
return the mid.Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to search for the target element in a rotated sorted array
int search(vector<int>& nums, int target) {
int low = 0, high = nums.size() - 1;
// Applying binary search algorithm
while (low <= high) {
int mid = low + (high - low) / 2;
// Check if mid points to the target
if (nums[mid] == target) return mid;
// Check if the left part is sorted
if (nums[low] <= nums[mid]) {
if (nums[low] <= target && target <= nums[mid]) {
// Target exists in the left sorted part
high = mid - 1;
} else {
// Target does not exist in the left sorted part
low = mid + 1;
}
} else {
// Check if the right part is sorted
if (nums[mid] <= target && target <= nums[high]) {
// Target exists in the right sorted part
low = mid + 1;
} else {
// Target does not exist in the right sorted part
high = mid - 1;
}
}
}
// If target is not found
return -1;
}
};
int main() {
vector<int> nums = {7, 8, 9, 1, 2, 3, 4, 5, 6};
int target = 1;
// Create an instance of the Solution class
Solution sol;
// Function call to search for the target element
int result = sol.search(nums, target);
if (result == -1)
cout << "Target is not present.\n";
else
cout << "The index is: " << result << "\n";
return 0;
}Complexity Analysis:
- Time Complexity:
O(logN), as the search space is reduced logarithmically, where N is the size of the given array. - Space Complexity:
O(1), not using any extra data structure.