Problem Explanation

The problem is about searching for a target value in a sorted array that has been rotated. You are given a list of sorted integers that has been shifted at some pivot point unknown to you in advance. Your job is to find a given number in the rotated array and return its index. If the number isn't in the list, return -1.

The sorting of the array from low to high is interrupted at a pivot point, which could be any index in the array. Despite the interruption, each part of the array is independently sorted.

The maximum time complexity of the algorithm should be in the order of O(log n).

Let's say, for example, we have a sorted array [0,1,2,4,5,6,7] that has been rotated to [4,5,6,7,0,1,2]. Our task is to find the index of 0 in the rotated array, which is 4.

Solution Approach

Since the left and right halves of the array are sorted, we can use binary search to find the target value.

We divide the array into two halves, left and right, with m as the middle index. If the number at index m is equal to the target, we simply return m.

If the numbers from l to m are sorted, i.e., nums[l] <= nums[m], and the target lies within these numbers (i.e., nums[l] <= target < nums[m]), we discard the right half and continue our search in the left half (r = m - 1). This is because the target, if it exists, must be in the sorted left half. Otherwise, we narrow our search to the right half (l = m + 1).

If the numbers from m to r are sorted (i.e., nums[l] > nums[m]) and the target lies within these numbers (i.e., nums[m] < target <= nums[r]), we discard the left half and continue our search in the right half (l = m + 1). Otherwise, we narrow our search to the left half (r = m - 1).

If we can't find the target after examining all elements of the array, we return -1.

Python Solution

1
2python
3class Solution:
4    def search(self, nums: List[int], target: int) -> int:
5        l, r = 0, len(nums) - 1
6        while l <= r:
7            m = (l + r) // 2
8            if nums[m] == target:
9                return m
10            if nums[l] <= nums[m]:
11                if nums[l] <= target < nums[m]:
12                    r = m - 1
13                else:
14                    l = m + 1
15            else:
16                if nums[m] < target <= nums[r]:
17                    l = m + 1
18                else:
19                    r = m - 1
20        return -1

Java Solution

1
2java
3class Solution {
4    public int search(int[] nums, int target) {
5        int l = 0, r = nums.length - 1;
6        while (l <= r) {
7            int m = l + (r - l) / 2;
8            if (nums[m] == target) return m;
9            if (nums[l] <= nums[m]) {
10                if (nums[l] <= target && target < nums[m]) r = m - 1;
11                else l = m + 1;
12            } else {
13                if (nums[m] < target && target <= nums[r]) l = m + 1;
14                else r = m - 1;
15            }
16        }
17        return -1;
18    }
19}

JavaScript Solution

1
2javascript
3var search = function(nums, target) {
4    let start = 0, end = nums.length - 1;
5    while (start <= end) {
6        let mid = start + Math.floor((end - start) / 2);
7        if (nums[mid] === target) return mid;
8        if (nums[start] <= nums[mid]) {
9            if (target >= nums[start] && target < nums[mid]) end = mid - 1;
10            else start = mid + 1;
11        } else {
12            if (target <= nums[end] && target > nums[mid]) start = mid + 1;
13            else end = mid - 1;
14        }
15    }
16    return -1;
17};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int search(vector<int>& nums, int target) {
6        int l = 0, r = nums.size() - 1;
7        while (l <= r) {
8            int m = l + (r - l) / 2;
9            if (nums[m] == target) return m;
10            if (nums[l] <= nums[m]) {
11                if (target >= nums[l] && target < nums[m]) r = m - 1;
12                else l = m + 1;
13            } else {
14                if (target <= nums[r] && target > nums[m]) l = m + 1;
15                else r = m - 1;
16            }
17        }
18        return -1;
19    }
20};

C# Solution

1
2csharp
3public class Solution {
4    public int Search(int[] nums, int target) {
5        int l = 0, r = nums.Length - 1;
6        while (l <= r) {
7            int m = l + (r - l) / 2;
8            if (nums[m] == target) return m;
9            if (nums[l] <= nums[m]) {
10                if (target >= nums[l] && target < nums[m]) r = m - 1;
11                else l = m + 1;
12            } else {
13                if (target <= nums[r] && target > nums[m]) l = m + 1;
14                else r = m - 1;
15            }
16        }
17        return -1;
18    }
19}

In conclusion, the crux of the solution is to use binary search and determine in which segment of the array the element could be present. This allows us to discard the segment where the element cannot be present, eventually helping us find the target index if it is present in the list.

The implementations provided above utilize binary search to check whether the target is present in the sorted half of the array. If not, they shift the search to the other half. This way, at each step, we are reducing the size of the search space by half, resulting in a time complexity of O(log n), which is much more efficient than linear search(O(n)) for large arrays.

Since binary search is a widely used algorithm for sorted arrays, understanding the details of this problem and its solution will also be beneficial as a general binary search problem-solving strategy. It broadens our view beyond the standard binary search problems, and enable us to deal with more complex situations such as this one where a sorted array is rotated.

So go ahead and practice this problem. Happy coding!