33. 搜索旋转排序数组

题目描述

有一个元素互不相同的升序数组。它在某个未知下标 k（0 <= k < nums.length）处被向左旋转：从 nums[k] 到末尾的部分被整体移到了前面。例如 [0,1,2,4,5,6,7] 在下标 3 处旋转后变成 [4,5,6,7,0,1,2]。

输入旋转后的数组 nums 和整数 target。若 target 在 nums 中，返回它的下标（从 0 开始）；否则返回 -1。

要求时间复杂度为 O(log n)。

示例 1

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

解释：0 位于下标 4。

示例 2

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

解释：数组中没有 3。

示例 3

输入：nums = [1], target = 0
输出：-1

解释：数组中没有 0。

数据范围

1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中的值互不相同。
nums 是升序数组在某个未知下标处旋转后得到的。
-10^4 <= target <= 10^4

解题思路：一次二分判断有序半边

判断哪一半有序后缩区间。

为什么正确

区间若有答案则始终保留它。

复杂度分析

时间 O(log n)，额外空间 O(1)。

易错点

注意边界条件并在回溯或弹出后恢复状态。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
 def search(self,a,t):
  l,h=0,len(a)-1
  while l<=h:
   m=(l+h)//2
   if a[m]==t:return m
   if a[l]<=a[m]:
    if a[l]<=t<a[m]:h=m-1
    else:l=m+1
   elif a[m]<t<=a[h]:l=m+1
   else:h=m-1
  return -1

class Solution {
    public int search(int[] nums, int target) {
        int l = 0, h = nums.length - 1;
        while (l <= h) {
            int m = (l + h) / 2;
            if (nums[m] == target) return m;
            if (nums[l] <= nums[m]) {
                if (nums[l] <= target && target < nums[m]) h = m - 1;
                else l = m + 1;
            } else if (nums[m] < target && target <= nums[h]) l = m + 1;
            else h = m - 1;
        }
        return -1;
    }
}

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, h = nums.size() - 1;
        while (l <= h) {
            int m = (l + h) / 2;
            if (nums[m] == target) return m;
            if (nums[l] <= nums[m]) {
                if (nums[l] <= target && target < nums[m]) h = m - 1;
                else l = m + 1;
            } else if (nums[m] < target && target <= nums[h]) l = m + 1;
            else h = m - 1;
        }
        return -1;
    }
};

func search(nums []int, target int) int {
	l, h := 0, len(nums)-1
	for l <= h {
		m := (l + h) / 2
		if nums[m] == target {
			return m
		}
		if nums[l] <= nums[m] {
			if nums[l] <= target && target < nums[m] {
				h = m - 1
			} else {
				l = m + 1
			}
		} else if nums[m] < target && target <= nums[h] {
			l = m + 1
		} else {
			h = m - 1
		}
	}
	return -1
}

var search = function(nums, target) {
    let l = 0, h = nums.length - 1;
    while (l <= h) {
        const m = (l + h) >> 1;
        if (nums[m] === target) return m;
        if (nums[l] <= nums[m]) {
            if (nums[l] <= target && target < nums[m]) h = m - 1;
            else l = m + 1;
        } else if (nums[m] < target && target <= nums[h]) l = m + 1;
        else h = m - 1;
    }
    return -1;
};

function search(nums: number[], target: number): number {
    let l = 0, h = nums.length - 1;
    while (l <= h) {
        const m = (l + h) >> 1;
        if (nums[m] === target) return m;
        if (nums[l] <= nums[m]) {
            if (nums[l] <= target && target < nums[m]) h = m - 1;
            else l = m + 1;
        } else if (nums[m] < target && target <= nums[h]) l = m + 1;
        else h = m - 1;
    }
    return -1;
};

载入编辑器，自己跑一遍 →

其他解法

两种方法都是 O(log n)；主解法在一次二分中同时判断哪一半有序，先找旋转点的做法用两次更简单的二分完成。

解法 2：先找旋转点再二分时间 O(log n)，空间 O(1)

第一次二分找最小值的下标 k：nums[m] > nums[h] 说明最小值在 m 右侧，否则在 m 或左侧。k 把数组分成 [0, k-1] 和 [k, n-1] 两个升序段。若 nums[k] ≤ target ≤ nums[n-1]，就在右段做普通二分，否则在左段做普通二分。

把问题拆成「寻找旋转排序数组中的最小值」和「普通二分」两个熟悉的子问题，每一步的判断更简单。要做两次二分，常数比主解法大一些。

class Solution:
    def search(self, nums, target):
        n = len(nums)
        l, h = 0, n - 1
        while l < h:
            m = (l + h) // 2
            if nums[m] > nums[h]:
                l = m + 1
            else:
                h = m
        k = l
        if nums[k] <= target <= nums[n - 1]:
            l, h = k, n - 1
        else:
            l, h = 0, k - 1
        while l <= h:
            m = (l + h) // 2
            if nums[m] == target:
                return m
            if nums[m] < target:
                l = m + 1
            else:
                h = m - 1
        return -1

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        int l = 0, h = n - 1;
        while (l < h) {
            int m = (l + h) / 2;
            if (nums[m] > nums[h]) l = m + 1;
            else h = m;
        }
        int k = l;
        if (nums[k] <= target && target <= nums[n - 1]) { l = k; h = n - 1; }
        else { l = 0; h = k - 1; }
        while (l <= h) {
            int m = (l + h) / 2;
            if (nums[m] == target) return m;
            if (nums[m] < target) l = m + 1;
            else h = m - 1;
        }
        return -1;
    }
}

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, h = n - 1;
        while (l < h) {
            int m = (l + h) / 2;
            if (nums[m] > nums[h]) l = m + 1;
            else h = m;
        }
        int k = l;
        if (nums[k] <= target && target <= nums[n - 1]) { l = k; h = n - 1; }
        else { l = 0; h = k - 1; }
        while (l <= h) {
            int m = (l + h) / 2;
            if (nums[m] == target) return m;
            if (nums[m] < target) l = m + 1;
            else h = m - 1;
        }
        return -1;
    }
};

func search(nums []int, target int) int {
	n := len(nums)
	l, h := 0, n-1
	for l < h {
		m := (l + h) / 2
		if nums[m] > nums[h] {
			l = m + 1
		} else {
			h = m
		}
	}
	k := l
	if nums[k] <= target && target <= nums[n-1] {
		l, h = k, n-1
	} else {
		l, h = 0, k-1
	}
	for l <= h {
		m := (l + h) / 2
		if nums[m] == target {
			return m
		}
		if nums[m] < target {
			l = m + 1
		} else {
			h = m - 1
		}
	}
	return -1
}

var search = function(nums, target) {
    const n = nums.length;
    let l = 0, h = n - 1;
    while (l < h) {
        const m = (l + h) >> 1;
        if (nums[m] > nums[h]) l = m + 1;
        else h = m;
    }
    const k = l;
    if (nums[k] <= target && target <= nums[n - 1]) { l = k; h = n - 1; }
    else { l = 0; h = k - 1; }
    while (l <= h) {
        const m = (l + h) >> 1;
        if (nums[m] === target) return m;
        if (nums[m] < target) l = m + 1;
        else h = m - 1;
    }
    return -1;
};

function search(nums: number[], target: number): number {
    const n = nums.length;
    let l = 0, h = n - 1;
    while (l < h) {
        const m = (l + h) >> 1;
        if (nums[m] > nums[h]) l = m + 1;
        else h = m;
    }
    const k = l;
    if (nums[k] <= target && target <= nums[n - 1]) { l = k; h = n - 1; }
    else { l = 0; h = k - 1; }
    while (l <= h) {
        const m = (l + h) >> 1;
        if (nums[m] === target) return m;
        if (nums[m] < target) l = m + 1;
        else h = m - 1;
    }
    return -1;
}

二分查找专题的其他题目

查看二分查找全部题目 →