The Binary Search Algorithm for Rotated Sorted Array


The Classic Binary Search Algorithm can be used for a sorted array. What about if the array is rotated sorted? For example, [4, 5, 6, 7, 0, 1, 2] is a rotated sorted array.

Suppose an array sorted in ascending order 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.

Your algorithm’s runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Can we still use the binary search with O(logN) complexity to search for particular item in the ‘sorted’ array? The answer is YES, however, we have to check which half region is strictly ascending. The rest is quite similar – see below Java implementation of Binary Search Algorithm for rotated sorted array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int search(int[] nums, int target) {
        int H = nums.length - 1;
        int low = 0, high = H;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (target == nums[mid]) {
                return mid;
            }
            if (nums[mid] < nums[high]) {
                if (target > nums[mid] && target <= nums[high]) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            } else { //  nums[low] < nums[mid]
                if (target >= nums[low] && target < nums[mid]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }                
            }
        }
        return -1;        
    }
}
class Solution {
    public int search(int[] nums, int target) {
        int H = nums.length - 1;
        int low = 0, high = H;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (target == nums[mid]) {
                return mid;
            }
            if (nums[mid] < nums[high]) {
                if (target > nums[mid] && target <= nums[high]) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            } else { //  nums[low] < nums[mid]
                if (target >= nums[low] && target < nums[mid]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }                
            }
        }
        return -1;        
    }
}

It turns out the Java implementation can be quickly and easily converted to C++ – the only core difference is the size() function to get the number of elements in the array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int H = nums.size() - 1;
        int low = 0, high = H;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (target == nums[mid]) {
                return mid;
            }
            if (nums[mid] < nums[high]) {
                if (target > nums[mid] && target <= nums[high]) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            } else { //  nums[low] < nums[mid]
                if (target >= nums[low] && target < nums[mid]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }                
            }
        }
        return -1;
    }
};
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int H = nums.size() - 1;
        int low = 0, high = H;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (target == nums[mid]) {
                return mid;
            }
            if (nums[mid] < nums[high]) {
                if (target > nums[mid] && target <= nums[high]) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            } else { //  nums[low] < nums[mid]
                if (target >= nums[low] && target < nums[mid]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }                
            }
        }
        return -1;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
428 words
Last Post: Number of Recent Calls - Queue Data Structure Exercise
Next Post: Computing History Museum

The Permanent URL is: The Binary Search Algorithm for Rotated Sorted Array

Leave a Reply