Category: binary search

Categories
binary search data structures java

search in rotated sorted array

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

1

Reference

binary search algorithm
Categories
binary search data structures java

binary search algorithm

Binary search algorithm is one of the fastest way to identify the element from an sorted array. It is also the commonly asked data structure interview questions.

It works based on divide and conquer mechanism. It will divide the given array into 2 parts and discard the one part. So it will works faster for a big array compared to linear search.

Time complexity of Binary Search is O(logn)

Below is the give array structure

With the above given array we have to find the position of 9, Using linear search we can find easily, But the time complexity will be O(N)

Below is java code snippet to find the position using Binary Search 

public class BinarySearchExample {

	private int binarySearch(int[] array, int target) {
		int leftIndex = 0;
		int rightIndex = array.length - 1;
		while (leftIndex <= rightIndex) {
			// find the middle Index
			int middleIndex = (leftIndex + rightIndex) / 2;
			if (array[middleIndex] == target) {
				return middleIndex;
			}
			if (target > array[middleIndex]) {
				// ignoring the left side of array
				leftIndex = middleIndex + 1;
			} else {
				// ignoring the right side of array
				rightIndex = middleIndex - 1;
			}
		}
		return -1;
	}

	public static void main(String[] args) {
		int[] i = { 2, 3, 5, 6, 7, 9,10 };
		int targetNumber = 9;
		BinarySearchExample object = new BinarySearchExample();
		int output = object.binarySearch(i, targetNumber);
		System.out.println(output);
	}

}
Output
5