Search in Rotated Array

This is part two of the DSA Series where we'll solve the 'Search in Rotated Array Problem'.

Problem Statement

Assume there is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array numsafter the possible rotation and an integer target, return the index oftargetif it is innums, or-1if it is not innums.

For example, input given to the function: nums = [4,5,6,7,0,1,2], target = 0

Output: 4

The question also specifies to write an algorithm of O(log n) runtime complexity.

As always, we will first go through the bruteforce approach and then optimise our solution.

The Bruteforce Solution

Our function will have two parameters, a rotated array of integers nums[] and a target. Let's breakdown the problem.

1. Find the index in the array nums[] from where the array has been pivoted / rotated. This will divide the original array into two smaller sorted arrays.

2. Look through each of these smaller arrays to find the target and return the index if found.

Our first task is to find the index at which the array has been rotated. Let's call this pivot_index. For example, in the array, nums = [4,5,3,7,0,1,2] the pivot_index is 4. This is because nums[4] = 0 and 0 is breaking the pattern and is dividing the whole array into two smaller sorted arrays [4,5,6,7] and [0,1,2].

To find our pivot_index, we will have to check if the ith element is smaller than the (i+1)th element or not. The code will be as follows:

// For finding the pivot index.

int x = 0; // a temporary variable used for comparison
int pivot_index = 0;
for (int i = 1; i < nums.length; i++) {
    if (nums[x] < nums[i]) {
        x++;
    } else {
        pivot_index = i;
        break;
    }
}

Feel free to dry run the above code a few times with different arrays for better understanding.

After finding our pivot_index, the next step is to simply loop through the two smaller sorted arrays to find our target. Note that all elements before and after the pivot_index are sorted as we discused in our example previously.

So the first loop will be from nums[0] upto nums[pivot_index] and the second loop will be from nums[pivot_index] to nums.length-1. Here is the code for the whole function:

public static int searchInRotatedArray(int nums[], int target) {
    // variable which returns index of target if in nums & 
    //returns -1 if target is not in nums
    int res = -1;

    // For finding pivot index
    int x = 0;
    int pivot_index = 0;
    for (int i = 1; i < nums.length; i++) {
        if (nums[x] < nums[i]) {
            x++;
        } else {
            pivot_index = i;
            break;
        }
    }

    // Searching all elements before pivot index
    for (int i = 0; i < pivot_index; i++) {
        if (nums[i] == target) {
            res = i;
            return res;
        }
    }

    // Searching all elements after pivot index
    for (int i = pivot_index; i < nums.length; i++) {
        if (nums[i] == target) {
            res = i;
            return res;
        }
    }

    return res;
}

Try to do a dry run with any array of your choice for better clarity. The above code does work but will give a take a lot of time considering larger arrays. So we can go for an even more optimised approach using binary search.

Optimised Solution using Binary Search

Our steps for solving the problem do remain the same, i.e. to find the pivot_index and then look through the two sorted arrays. The method for finding the pivot_index remains the same however we will search the arrays using binary search instead of loops.

The binary search algorithm is a very efficient way to traverse an array to find a particular element. We will not be going into the detailed code or explanation for the algorithm but it works by dividing the array into smaller and smaller segments until we reach our desired element.

Let us first create a separate function for binary search.

public static int binarySearch(int nums[], int start, int end, int target) {
    while (start <= end) {
        int mid = start + (end-start) / 2;

        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return -1;
    }

The above function takes in 4 parameters where int start is the index from where we have to start our binary search and int end is the index upto which we perform our search.

The only part I'd like to elaborate is line number 3. In our typical binary search algorithms we usually write int mid = (start+end) / 2 . But here we have written, int mid = start + (end-start) / 2 . This is to prevent overflow. In Java, int is a 32-bit integer, and adding two large integers could exceed the maximum value for an int (2^31 - 1). The second formula correctly calculates the middle index without overflow and ensures that mid is an integer value within the search range. end-start gives the distance between end and start. Dividing by 2 finds the middle distance and adding start to this middle distance gives the middle index.

Moving on, once we have written our function for binary search the last task is to determine which side of the array should we search for the target. The approach is same as before. If the target is greater than nums[0] and less than nums[pivot_index-1] it means that the target is present in the left half of the array. So we pass the starting index i.e. 0 and the ending index i.e. pivot_index-1 to our binarySearch function. And if the target is greater than nums[pivot_index] and less than nums[nums.length-1] it means that the target is present in the right half of the array. Then we pass appropriate starting and ending indexes to our binarySearch function.

Do keep in mind that we are dealing with two sorted arrays which are present before and after the pivot_index. Which is why we are comparing the values of the array with the target.

At last, we can also get a completely sorted array for example, nums = [1,3,5] which is already sorted. In this case, the pivot_index will be 0 and we can perform binarySearch on it as usual.

Here is the final optimised code:

public static int binarySearch(int nums[], int start, int end, int target) {
    while (start <= end) {
        int mid = start + (end-start) / 2;

        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return -1;
}

public static int searchInArray(int nums[], int target) {

    // To find pivot index
    int x = 0;
    int pivot_index = 0;
    for (int i = 1; i < nums.length; i++) {
        if (nums[x] < nums[i]) {
            x++;
        } else {
            pivot_index = i;
            break;
        }
    }

    // If array is not rotated i.e. it is a sorted array
    if (pivot_index == 0) {
        return binarySearch(nums, 0, nums.length-1, target);
    }

    // If target is at pivot index
    if (nums[pivot_index] == target) {
        return pivot_index;
    }

    // To determine which side to search
    if (target >= nums[0] && target <= nums[pivot_index-1]) { // When target is between nums[0] and nums[pivot_index], i.e. left half
        return binarySearch(nums, 0, pivot_index-1, target);
    } else { // When target is between pivot index and nums.length i.e. right half
        return binarySearch(nums, pivot_index, nums.length-1, target);
    }
}

That's a wrap for today. More to come :)