- brute force would be to just iterate through the array and check if the current value equals our target
- this will not fit the time complexity requirement of O(log n) however
- if the array was sorted, a binary search would be a simple solution
- maybe we can still employ binary search since the array is partially sorted
- the array also has two primary components based on where the rotation finishes
🤔What Did I Struggle With?
figuring out how to action the use of binary search in this case
💡 Explanation of Solution
1. use binary search to find the target
2. identify the sorted half: for each iteration determine whether the left or right half of the array is sorted by comparing nums[left] and nums[mid]
3. search in the sorted half
4. continue 2 and 3 until the target index is found or return 01
⌛ Complexity Analysis
Time Complexity: O(log n) based on the requireemnts of the problem
Space Compelxity: O(1)
💻 Implementation of Solution
class Solution {public: int search(vector<int>& 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 && nums[mid] >= target) right = mid -1; else left = mid + 1; } else { if(nums[right] >= target && nums[mid] <= target) left = mid + 1; else right = mid -1; } } return -1; }};