Question

Formatted question description: https://leetcode.ca/all/33.html

33. Search in Rotated Sorted Array

Level

Medium

Description

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

Solution

To solve the problem in O(log n) runtime complexity, use binary search. Since the sorted array is rotated at some pivot, the logic is a little different from traditional binary search.

Use two pointers low and high, which initially point to the begin and the end of the array respectively. The loop condition is low <= high. Each time choose mid as the average of low and high. If nums[mid] == target, then return mid. Otherwise, decide which half should be searched next, [low, mid - 1] or [mid + 1, high]. Two cases may exist. The first case is that nums[low] <= nums[mid], which means the rotation point is on the right of mid. Search in [low, mid - 1] if target is between nums[low] and nums[mid], and otherwise search in [mid + 1, high]. The first case is that nums[low] > nums[mid], which means the rotation pointer is on the left of mid. Search in [mid + 1, high] if target is between nums[mid] and nums[high], and otherwise search in [low, mid - 1]. If target is not found, return -1.

Code

public class Search_in_Rotated_Sorted_Array {

    // time: O(1)
    // space: O(N)
    public class Solution {

        public int search(int[] nums, int target) {

            if (nums == null || nums.length == 0) {
                return -1;
            }

            int i = 0; // left pointer
            int j = nums.length - 1; // right pointer

            while (i <= j) {
                int mid = (i + j) / 2; // @note: possible overflow, use: int mid = i + (j - i) / 2

                if (nums[mid] == target) {
                    return mid;
                }

		        /*
		            @note: I missed case when nums[mid] is the max of the values, then both mid-left-half and mid-right-half are ordered:
		                array=[3,5,1], target=1
		                array=[3,5,1], target=3
		
		                array=[4,5,6,  7,  1,2,3]
		
		            @note: question is, how to deal with case where mid-value is max-value?
		                    initially I was thinking compare mid with mid-1 value and mid+1 value, but tedious
		                    simple solution is, add another condition to make a range query:
		                        nums[i] < target and target < nums[mid]
		        */

                // @note: if (nums[0] <= nums[mid]) {
                if (nums[i] <= nums[mid]) { // left half ordered, right half not ordered

                    // if (target <= nums[mid]) {
                    if (nums[i] <= target && target <= nums[mid]) {
                        j = mid - 1;
                    } else {
                        // i++; //[NOT binary]
                        i = mid + 1;
                    }
                } else { // right half ordered, left half not ordered

                    // if (target <= nums[mid]) {
                    if (nums[mid] <= target && target <= nums[j]) {
                        i = mid + 1;
                    } else {
                        // j--; //[NOT binary]
                        j = mid - 1;
                    }
                }
            }

            return -1;
        }
    }
}

############

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target <= nums[mid]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
        }
        return nums[left] == target ? left : -1;
    }
}

// OJ: https://leetcode.com/problems/search-in-rotated-sorted-array/
// Time: O(logN)
// Space: O(1)
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty()) return -1;
        int L = 0, R = nums.size() - 1, pivot;
        while (L < R) {
            int M = L + (R - L) / 2;
            if (nums[M] < nums[R]) R = M;
            else L = M + 1;
        }
        pivot = L;
        if (pivot && target >= nums[0] && target <= nums[pivot - 1]) L = 0, R = pivot - 1;
        else L = pivot, R = nums.size() - 1;
        while (L <= R) {
            int M = L + (R - L) / 2;
            if (nums[M] == target) return M;
            if (target > nums[M]) L = M + 1;
            else R = M - 1;
        }
        return -1;
    }
};

# below 2 solutions, diff is while condition: left ('<' or '<=') right

# I like this better
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        left, right = 0, n - 1
        while left <= right:
            mid = (left + right) >> 1
            if nums[mid] == target:
                return mid
            elif nums[0] <= nums[mid]: # left half sorted
                if nums[0] <= target <= nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else: # right half sorted
                if nums[mid] < target <= nums[n - 1]:
                    left = mid + 1
                else:
                    right = mid -1
        return -1

############

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        left, right = 0, n - 1
        while left < right:
            mid = (left + right) >> 1
            if nums[0] <= nums[mid]: # left half sorted
                if nums[0] <= target <= nums[mid]:
                    right = mid
                else:
                    left = mid + 1
            else: # right half sorted
                if nums[mid] < target <= nums[n - 1]:
                    left = mid + 1
                else:
                    right = mid
        return left if nums[left] == target else -1

func search(nums []int, target int) int {
	n := len(nums)
	left, right := 0, n-1
	for left < right {
		mid := (left + right) >> 1
		if nums[0] <= nums[mid] {
			if nums[0] <= target && target <= nums[mid] {
				right = mid
			} else {
				left = mid + 1
			}
		} else {
			if nums[mid] < target && target <= nums[n-1] {
				left = mid + 1
			} else {
				right = mid
			}
		}
	}
	if nums[left] == target {
		return left
	}
	return -1
}

function search(nums: number[], target: number): number {
    const n = nums.length;
    let left = 0,
        right = n - 1;
    while (left < right) {
        const mid = (left + right) >> 1;
        if (nums[0] <= nums[mid]) {
            if (nums[0] <= target && target <= nums[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        } else {
            if (nums[mid] < target && target <= nums[n - 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
    }
    return nums[left] == target ? left : -1;
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
    const n = nums.length;
    let left = 0,
        right = n - 1;
    while (left < right) {
        const mid = (left + right) >> 1;
        if (nums[0] <= nums[mid]) {
            if (nums[0] <= target && target <= nums[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        } else {
            if (nums[mid] < target && target <= nums[n - 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
    }
    return nums[left] == target ? left : -1;
};

impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let mut l = 0;
        let mut r = nums.len() - 1;
        while l <= r {
            let mid = l + r >> 1;
            if nums[mid] == target {
                return mid as i32;
            }

            if nums[l] <= nums[mid] {
                if target < nums[mid] && target >= nums[l] {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if target > nums[mid] && target <= nums[r] {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        -1
    }
}

33 - Search in Rotated Sorted Array

Question

33. Search in Rotated Sorted Array

Level

Description

Solution

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

33. Search in Rotated Sorted Array

Level

Description

Solution

Code

All Problems

All Solutions