CC-15 : Search number in rotated sorted array.

Description:

A rotated sorted array can wrap around its last and first index:
303, 418, 673, 3, 22, 44, 67, 77, 96, 122, 144, 201,
In this array, 3 is the smallest element/ first element of rotated sorted array and 673 is largest/last element of rotated sorted array.
Given a input number and rotated sorted array, find the number in the array.

Test cases and expected outputs:

Input Parameters	Expected outputs
Array: 303, 418, 673, 3, 22, 44, 67, 77, 96, 122, 144, 201,	67 found at index 6 418 found at index 1

Pseudocode:

searchInRotatedSortedArray (nums[], toSearch):

Integer array named nums and integer named toSearch to be searched are received as input parameters.

Set integer variable firstIdx to zero, we will use this variable to check the first index of partition in which are searching for required integer.

Set integer variable lastIdx to nums.length-1, we will use this variable to check the last index of partition in which are searching for required integer.

While (firstIdx <= lastIdx) do the following steps:

Set integer variable midIdx to (lastIdx-firstIdx)/2. We will use midIdx to partition the array into 2 partitions.

If (nums[0]==nums[midIdx) :

Set lastIdx to midIdx.

Else:

Set firstIdx to midIdx+1.

Else if nums[midIdx] < toSearch and toSearch < nums[nums.length-1] then:

Set firstIdx=midIdx+1, as we need to search in the higher partition now.

Else:

Set lastIdx=(midIdx) as we need to search in lower partition now.

Set variable searchIdx to -1.

If nums[firstIdx]=toSearch, set searchIdx equal to firstIdx.

Else set searchIdx=-1.

Return searchIdx.

Code:

public int searchInRotatedSortedArray(int[] nums, int toSearch){
	int firstIdx=0;
	int lastIdx=nums.length-1;
	while (firstIdx < lastIdx) {
		int midIdx=(lastIdx+firstIdx)/2;
		if (nums[0]<=nums[midIdx]) {
			if ((nums[0] < toSearch)&&(toSearch <= nums[midIdx])){
				lastIdx=midIdx;
			}else {
				firstIdx=midIdx+1;
			}
		} else { 
			if ((nums[midIdx] < toSearch)&&(toSearch <= nums[nums.length-1])) {
			firstIdx=midIdx+1;
		}else {
			lastIdx=midIdx;
		}
		}		
	}	
	int searchIdx=-1;
	if (nums[firstIdx]==toSearch) {
		searchIdx=firstIdx;
	}else {
		searchIdx=-1;
	}
	return searchIdx;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class SearchInRotatedSortedArray {

public int searchInRotatedSortedArray(int[] nums, int toSearch){
	int firstIdx=0;
	int lastIdx=nums.length-1;
	while (firstIdx < lastIdx) {
		int midIdx=(lastIdx+firstIdx)/2;
		if (nums[0]<=nums[midIdx]) {
			if ((nums[0] < toSearch)&&(toSearch <= nums[midIdx])){
				lastIdx=midIdx;
			}else {
				firstIdx=midIdx+1;
			}
		} else { 
			if ((nums[midIdx] < toSearch)&&(toSearch <= nums[nums.length-1])) {
			firstIdx=midIdx+1;
		}else {
			lastIdx=midIdx;
		}
		}		
	}	
	int searchIdx=-1;
	if (nums[firstIdx]==toSearch) {
		searchIdx=firstIdx;
	}else {
		searchIdx=-1;
	}
	return searchIdx;
}

public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	int retVal;
	try {
	
	SearchInRotatedSortedArray search=new SearchInRotatedSortedArray();
	int[] nums= { 303,418, 673, 3,22,44,67,77,96,122,144,201};
	int toSearch=67;
	retVal=search.searchInRotatedSortedArray(nums, toSearch);
	
	System.out.println("\nArray:");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < nums.length; arrayIndex++) {
		System.out.print(nums[arrayIndex]+", ");		
	} 
	
	System.out.println("\n\n"+toSearch + " found at index "+ retVal);	
	
	toSearch=418;
	retVal=search.searchInRotatedSortedArray(nums, toSearch);
	System.out.println("\n\n"+toSearch + " found at index "+ retVal);	
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}


}