33. Search in Rotated Sorted Array

Problem

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.

Related Topics:

Array Binary Search

Analysis

方法一：先找出最小值所在的下标，确定目标在哪一边，然后进行二分查找。

方法二：当 target < nums[mid] 时，存在三种情况。

• 两则都在分割线（最小值与最大值之间）的左边：为升序，target 在 nums[mid] 左边，所以 nums[mid] 右边的元素舍弃，即 end = mid - 1。

• 两则都在分割线的右边：为升序，同上，end = mid - 1。

• 由于分割线左边元素大于右边，所以 target 在右边，nums[mid] 在左边：舍弃 nums[mid] 左边元素，即 start = mid + 1。

同理，target > nums[mid] 时，也有三种情况，处理方法类似。

Code

找最小值：

class Solution {

    fun search(nums: IntArray, target: Int): Int {

        if (nums.isEmpty()) return -1

        val minIndex = findMin(nums)
        var start: Int
        var end: Int
        var mid: Int

        when {
            target > nums[nums.lastIndex] -> {
                start = 0
                end = minIndex - 1
            }
            else -> {
                start = minIndex
                end = nums.lastIndex
            }
        }

        while (start <= end) {
            mid = (start + end) / 2
            when {
                target == nums[mid] -> return mid
                target < nums[mid] -> end = mid - 1
                target > nums[mid] -> start = mid + 1
            }
        }

        return -1
    }

    private fun findMin(nums: IntArray): Int {

        var start = 0
        var end = nums.lastIndex
        var mid: Int

        while (start < end) {
            mid = (start + end) / 2
            when {
                nums[mid] > nums[end] -> start = mid + 1
                else -> end = mid
            }
        }

        return start
    }
}

所有情况判断：

class Solution {

    fun search(nums: IntArray, target: Int): Int {

        var start = 0
        var end = nums.lastIndex
        var mid: Int

        while (start <= end) {

            mid = (start + end) / 2

            when {
                target > nums[end] && nums[mid] <= nums[end] -> end = mid - 1
                target <= nums[end] && nums[mid] > nums[end] -> start = mid + 1
                else -> {
                    when {
                        target < nums[mid] -> end = mid - 1
                        target > nums[mid] -> start = mid + 1
                        else -> return mid
                    }
                }
            }
        }

        return -1
    }
}