Search in a Rotated Array

Coding Sep 06, 2020

Introduction

This problem deals with searching an element in a sorted array which is rotated once. The pivot is unknown to us.

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Approach

One approach that might come up is to run the binary search to find the pivot and then search the element.


The interesting property of a sorted and rotated array is that when you divide it into two halves, atleast one of the two halves will always be sorted.
We can use this property and code it to search in the sorted half or non-sorted half. Refer to the program below that uses O(log n) time complexity and O(1) memory.

using System;
public class GFG {
	static public void Main () {
	    var t = int.Parse(Console.ReadLine());
	    while (t > 0) {
	        var n = int.Parse(Console.ReadLine());
	        var a = new int[n];
	        var aStr = Console.ReadLine().Split(" ");
	        for (var i = 0; i < n; i++) {
	            a[i] = int.Parse(aStr[i]);
	        }
	        var k = int.Parse(Console.ReadLine());
	        Console.WriteLine(SearchRotated(a, 0, n - 1, k));
	        t--;
	    }
	}
	private static int SearchRotated(int[] a, int s, int e, int k) {
	    if (s > e) {
	        return -1;
	    }
	    var m = (e - s) / 2 + s;

	    if (a[m] == k) {
	        return m;
	    }

	    // first half is sorted
	    if (a[s] <= a[m]) {
	        if (a[s] <= k && a[m] >= k) {
	            return SearchRotated(a, s, m - 1, k);
	        } else {
	            return SearchRotated(a, m + 1, e, k);
	        }
	    }

	    // second half is sorted
            if (a[m] <= k && a[e] >= k) {
                return SearchRotated(a, m + 1, e, k);
            } else {
                return SearchRotated(a, s, m - 1, k);
            }
	}
}
C# Program to perform Binary Search in Rotated Sorted Array