Search in Rotated Sorted Array

Question:

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

解法代码

public class LeetCode33 {
    /**
     * 二分查找，递归
     * 理清思路，列举所有可能的情况，
     * 每一次二分可能有一半是有序集合一半是反转集合，也有可能两边都是有序集合
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        // 空数组，直接返回-1
        if(nums == null || nums.length == 0) {
            return -1;
        }
        return search(nums, 0, nums.length - 1, target);
    }
    
    private int search(int[] nums, int start, int end ,int target) {
        if(nums[start] == target) {
            return start;
        }
        if(nums[end] == target) {
            return end;
        }
        // 未找到结果
        if(end - start <= 1) {
            return -1;
        }
        int mid = (start + end + 1) / 2;
        if(nums[mid] == target) {
            return mid;
        }
        // 结果在左半部分有序集中
        if(nums[start] < nums[mid] && target > nums[start] && target < nums[mid]) {
            return search(nums, start, mid, target);
        }
        
        // 结果在右半部分有序集中
        if(nums[mid] < nums[end] && target > nums[mid] && target < nums[end]) {
            return search(nums, mid, end, target);
        }
        
        // 结果在左半部分反转集中
        if(nums[start] > nums[mid]) {
            return search(nums, start, mid, target);
        }
        
        // 结果在有半部分反转集中
        return search(nums, mid, end, target);
    }
}

解法代码

import org.junit.Before;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;
import org.junit.runners.Parameterized.Parameters;

import static org.junit.Assert.assertEquals;

import java.util.Arrays;
import java.util.Collection;

import com.kay.pro.alog.LeetCode33;

@RunWith(Parameterized.class)
public class LeetCode33Test {
    private LeetCode33 leetCode;
    private int[] nums;
    private int target;
    private int index;
    
    public LeetCode33Test(int[] nums, int target, int index) {
        this.nums = nums;
        this.target = target;
        this.index = index;
    }
    
    @Before
    public void before() {
        leetCode = new LeetCode33();
    }
    
    @Parameters
    public static Collection<?> reverserArrays() {
        return Arrays.asList(new Object[][]{
            {new int[]{4, 5, 6, 7, 0, 1, 2}, 0, 4},
            {new int[]{4, 5, 6, 7, 0, 1, 2}, 3, -1},
            {new int[]{4, 5, 6, 7, 0, 1, 2}, 6, 2},
            {new int[]{8, 7, 6, 5, 4, 3, 2, 1, 0}, 6, 2}
        });
    }
    
    @Test
    public void leetCode33() {
        assertEquals(index, leetCode.search(nums, target));
    }
}

Output：

Time And Space Complexity

Time: 二分查找时间复杂度
Space: 不需要使用额外的存储空间，原地替换

Tips

二分查找，递归
理清思路，列举所有可能的情况，每一次二分可能有一半是有序集合一半是反转集合，也有可能两边都是有序集合