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] 时,存在三种情况。

  • 两则都在分割线(最小值与最大值之间)的左边:为升序,targetnums[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
    }
}

Last updated