Searching elements in sorted rotated array.

+1 vote
asked in Interview Question by nitin2604

Search given element in sorted array, which is rotated and print its position. Consider all elements in the given array are distinct.

The time complexity should be O(logn).

15 16 17 18 19 20 11 12 13 14



Search element 18  ?

Answer = 3 (index).

Add question to:
commented by shivani
We first need to search pivot element  in this rotated array and then we can search that element in the sorted sub array.
http://www.waytocrack.com/forum/394/search-pivot-element-in-a-rotated-sorted-array
commented by nitin2604
Hi, Shivani please check this approach, slightly different.

1 Answer

+4 votes
answered by nitin2604
selected by nitin2604
 
Best answer

Logic :

  1. Find the middle element of array.
          Mid = (low+high) /2
  1. Check for the sorted portion of array(Note: There will be always a sorted portion if you divide this array in two parts ) either array[low] to array[mid] or array[mid] to array[high].
  2. If array[low] to array[mid] sorted and key is also present then recur array[low] to array[mid]. Otherwise recur array[mid] to array[high].
  3. .Otherwise, if array[mid] to array[high] sorted and key is present within this range then recur array[mid] to array[high].
  4. Otherwise, recur array[low] to array[mid].

The base condition of recursion is

if (input_Arr[mid] == search_key)
		return mid;

This is the small example:

15, 16, 17, 18, 19, 20, 11, 12, 13, 14

Lets take the key as 18.

Middle = (low + high) /2, so middle element here is 19.

Now, check on which side key lies. Left side or right side and recur it into that direction.

Here the element must be on left side of the middle element. So, again do recursion till it reaches to the key element.

Check here for another solution of this problem.

Time complexity of this problem is O(logn)

Another corner case example is 9,10,11,1,2,3,4,5,6,7,8, please see this example in code and try to understand, comment if there is doubt in logic.

Search element in sorted rotated array code

//searching element in given sorted rotated array.
//all the elements in  the array should be distinct
// Time complexity of the code is O(logn).
#include "iostream"
using namespace std;

int find_element_fun(int * input_Arr, int low, int high, int search_key){
	if (low > high)
	{
		cout << " Value Not found " << endl;
		return -1;
	}

	//finding the mid element
	int mid = (low + high) / 2;
	
	//base case condition
	if (input_Arr[mid] == search_key)
		return mid;

	// checking for the sorted array.
	if (input_Arr[low] <= input_Arr[mid])
	{
		if (input_Arr[low] <= search_key && input_Arr[mid] >= search_key)
			
			return find_element_fun(input_Arr, low, mid - 1, search_key);
		return find_element_fun(input_Arr, mid + 1, high, search_key);
	}

	if (input_Arr[mid] <= search_key && input_Arr[high] >= search_key)
		return find_element_fun(input_Arr, mid + 1, high, search_key);
	return find_element_fun(input_Arr, low, mid - 1, search_key);
}

int main(){
	//int input_Arr[] = { 15, 16, 17, 18, 19, 20, 11, 12, 13, 14 };
	int input_Arr[] = {9,10,11,1,2,3,4,5,6,7,8};
	int search_Key = 11;
	//cin >> search_Key;
	int length = sizeof(input_Arr) / sizeof(input_Arr[0]);
	cout << find_element_fun(input_Arr, 0, length-1, search_Key) << endl;;
}

 

commented by shivani
Hi nitin2604, I got your logic and it is much better than i discussed.But I think your english and explanation is very poor.It is such a pain to get what you want to convey.Anyway, thanks for this great solution.
commented by nitin2604
Ok i'll work on this ... and give a much better explanation.
commented by shivani
It would be really great for the normal coders.
This line is very hard to get
"If left to middle element is sorted and the key is present within this range then recur on left array, otherwise recur from middle to right element."
...