LeetCode- Search in Rotated Sorted Array

Tags: , ,

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

  (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

  You are given a target value to search. If found in the array return its index, otherwise return -1.

  You may assume no duplicate exists in the array.

Leetcode- search in rotated sorted array

Using the idea of binary search, we can reduce the search space based on which range the target value is located. 

We first get the mid index of the array,

If it is value is larger than the beginning of the array, mid is in the left part (The Red bar).

Else the mid is in the right part (the green bar)

Now we can check the range of the target value further. 

Suppose mid is on the Red bar:

If target is less than the value of the Red bar, we can safely remove the right part of the array.

If target is larger than the value of the Red bar, we can safely remove the left part of the array. 

The following is the implementation in Java: