33. Search in Rotated Sorted Array (Medium)

https://leetcode.com/problems/search-in-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

Solutions

class Solution {
    public int search(int[] nums, int target) {
        int len = nums.length;

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

        if (len == 1) {
            return nums[0] == target ? 0 : -1;
        }

        int left = 0;
        int right = len - 1;

        // first find the rotated index
        int rindex = 0;

        while (left < right) {
            int mid = (left + right) / 2;

            if (nums[mid] > nums[mid + 1]) {
                rindex = mid + 1;
                break;
            }

            if (nums[mid] > nums[right]) {
                left = mid;
            }

            if (nums[mid] < nums[right]) {
                right = mid;
            }
        }

        if (rindex == 0) { // not rotated
            left = 0;
            right = len - 1;
        } else if (nums[len - 1] < target) { // on left part
            left = 0;
            right = rindex - 1;
        } else { // on right part, rindex != 0 && nums[len-1] > target
            left = rindex;
            right = len - 1;
        }

        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            }

            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return -1;
    }
}

Rferences

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:18

results matching ""

    No results matching ""