search in rotated sorted array

In this post we will discuss about search in rotated sorted array in efficient way using java

Problem Statement

Input: rotated sorted array
Time Complexity: O(logn)
Efficient Approach: Binary Search

Test Case 1
Input: { 7, 8, 0, 1, 2, 3, 4, 5, 6 }
Target: 8
Output: 1

Test Case 2
Input: { 7, 8, 0, 1, 2, 3, 4, 5, 6 }
Target: 100
Output: -1

Explanation

Consider that array doesn’t have duplicates
As initial step, we are going to let left pointer =0 & right pointer = array.lenght-1
As per binary search we are going to find the mid of the array
In case target value matches mid value, then return the mid
find the left and right position based on the below solution in iterative way

Solution


public class RotatedBinarySearchExample {

	private int rotatedBinarySearch(int[] nums, int target) {

		// Basic check 
		if (null == nums || nums.length == 0) {
			return -1;
		}
		if (nums.length == 1 && nums[0] == target) {
			return 0;
		}

		int mid = 0;
		int leftPointer = 0;
		int rightPointer = nums.length - 1;

		while (leftPointer <= rightPointer) {

			mid = (leftPointer + rightPointer) / 2;

			if (nums[mid] == target) {
				return mid;
			} else if (nums[leftPointer] <= nums[mid]) { 
				if (target >= nums[leftPointer] && target <= nums[mid]) {
					rightPointer = mid - 1;
				} else {
					leftPointer = mid + 1;
				}

			} else {
				if (target >= nums[mid] && target <= nums[rightPointer]) {
					leftPointer = mid + 1;
				} else {
					rightPointer = mid - 1;
				}
			}
		}
		return -1;
	}

	public static void main(String[] args) {
		RotatedBinarySearchExample rotatedBinarySearchExample = new RotatedBinarySearchExample();
		int[] array = { 7, 8, 0, 1, 2, 3, 4, 5, 6 };
		int targetNumber = 8;
		int output = rotatedBinarySearchExample.rotatedBinarySearch(array, targetNumber);
		System.out.println(output);
	}

}

Output

Reference

binary search algorithm