二分查找：求解《33. 搜索旋转排序数组》和《153. 寻找旋转排序数组中的最小值》
2022-06-14 17:11:51
二分查找，求解《33. 搜索旋转排序数组》
例题
33. 搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
答案
二分查找
var search = function(nums, target) {
let n = nums.length, l = 0, r = n - 1
while (l <= r) {
const m = l + r >>> 1
if (nums[m] === target) return m
if (nums[m] >= nums[0]) {
if (nums[m] < target || nums[0] > target) l = m + 1
else r = m - 1
} else {
if (nums[m] > target || nums[n - 1] < target) r = m - 1
else l = m + 1
}
}
return -1
};function search(nums: number[], target: number): number {
const n = nums.length
let l = 0, r = n - 1
while (l <= r) {
const m = l + r >>> 1
if (nums[m] === target) return m
if (nums[m] >= nums[0]) {
if (nums[m] < target || nums[0] > target) l = m + 1
else r = m - 1
} else {
if (nums[m] > target || nums[n - 1] < target) r = m - 1
else l = m + 1
}
}
return -1
};func search(nums []int, target int) int {
n := len(nums)
l, r := 0, n - 1
for l <= r {
m := (l + r) >> 1
if nums[m] == target {
return m
}
if nums[m] >= nums[0] {
if nums[m] < target || nums[0] > target {
l = m + 1
} else {
r = m - 1
}
} else {
if nums[m] > target || nums[n - 1] < target {
r = m - 1
} else {
l = m + 1
}
}
}
return -1
}class Solution {
function search($nums, $target) {
$n = count($nums);
$l = 0;
$r = $n - 1;
while ($l <= $r) {
$m = $l + $r >> 1;
if ($nums[$m] === $target) return $m;
if ($nums[$m] >= $nums[0]) {
if ($nums[$m] < $target || $nums[0] > $target) {
$l = $m + 1;
} else {
$r = $m - 1;
}
} else {
if ($nums[$m] > $target || $nums[$n - 1] < $target) {
$r = $m - 1;
} else {
$l = $m + 1;
}
}
}
return -1;
}
}class Solution:
def search(self, nums: List[int], target: int) -> int:
n = len(nums)
l, r = 0, n - 1
while l <= r:
m = l + r >> 1
if nums[m] == target: return m
if nums[m] >= nums[0]:
if nums[m] < target or nums[0] > target: l = m + 1
else: r = m - 1
else:
if nums[m] > target or nums[n - 1] < target: r = m - 1
else: l = m + 1
return -1 class Solution {
public int search(int[] nums, int target) {
int n = nums.length, l = 0, r = n - 1;
while (l <= r) {
int m = l + r >>> 1;
if (nums[m] == target) return m;
if (nums[m] >= nums[0]) {
if (nums[m] < target || nums[0] > target) {
l = m + 1;
} else {
r = m - 1;
}
} else {
if (nums[m] > target || nums[n - 1] < target) {
r = m - 1;
} else {
l = m + 1;
}
}
}
return - 1;
}
}153. 寻找旋转排序数组中的最小值
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
答案
二分查找 · 递归
var findMin = function(nums) {
const d = (l, r) => {
if (l > r) return nums[r]
const m = l + r >>> 1
if (nums[m] >= nums[0]) return Math.min(nums[0], d(m + 1, r))
return Math.min(nums[m], d(l, m - 1))
}
return d(0, nums.length - 1)
};function findMin(nums: number[]): number {
const d = (l: number, r: number): number => {
if (l > r) return nums[r]
const m = l + r >>> 1
if (nums[m] >= nums[0]) return Math.min(nums[0], d(m + 1, r))
return Math.min(nums[m], d(l, m - 1))
}
return d(0, nums.length - 1)
};func findMin(nums []int) int {
var d func(l int, r int) int
d = func(l int, r int) int {
if l > r {
return nums[r]
}
m := (l + r) >> 1
if nums[m] >= nums[0] {
return min(nums[0], d(m + 1, r))
}
return min(nums[m], d(l, m - 1))
}
return d(0, len(nums) - 1)
}
func min(a int, b int) int {
if a < b {
return a
}
return b
}class Solution {
function findMin($nums) {
return $this->d($nums, 0, sizeof($nums) - 1);
}
function d(&$nums, $l, $r) {
if ($l > $r) return $nums[$r];
$m = $l + $r >> 1;
if ($nums[$m] >= $nums[0]) return min($nums[0], $this->d($nums, $m + 1, $r));
return min($nums[$m], $this->d($nums, $l, $m - 1));
}
}class Solution {
private int[] ns;
public int findMin(int[] nums) {
ns = nums;
return d(0, nums.length - 1);
}
public int d(int l, int r) {
if (l > r) return ns[r];
int m = l + r >>> 1;
if (ns[m] >= ns[0]) return Math.min(ns[0], d(m + 1, r));
return Math.min(ns[m], d(l, m - 1));
}
}class Solution:
def findMin(self, nums: List[int]) -> int:
def d(l, r):
if l > r: return nums[r]
m = l + r >> 1
if nums[m] >= nums[0]:
return min(nums[0], d(m + 1, r))
return min(nums[m], d(l, m - 1))
return d(0, len(nums) - 1)二分查找 · 迭代
var findMin = function(nums) {
let l = 0, r = nums.length - 1
while (l < r) {
const m = l + r >>> 1
if (nums[m] < nums[r]) r = m
else l = m + 1
}
return nums[l]
};function findMin(nums: number[]): number {
let l = 0, r = nums.length - 1
while (l < r) {
const m = l + r >>> 1
if (nums[m] < nums[r]) r = m
else l = m + 1
}
return nums[l]
};func findMin(nums []int) int {
l, r := 0, len(nums) - 1
for l < r {
m := (l + r) >> 1
if nums[m] < nums[r] {
r = m
} else {
l = m + 1
}
}
return nums[l]
}class Solution {
function findMin($nums) {
$l = 0;
$r = count($nums) - 1;
while ($l < $r) {
$m = $l + $r >> 1;
if ($nums[$m] < $nums[$r]) $r = $m;
else $l = $m + 1;
}
return $nums[$l];
}
}class Solution {
public int findMin(int[] nums) {
int l = 0, r = nums.length - 1;
while (l < r) {
int m = l + r >>> 1;
if (nums[m] < nums[r]) r = m;
else l = m + 1;
}
return nums[l];
}
}class Solution:
def findMin(self, nums: List[int]) -> int:
l, r = 0, len(nums) - 1
while l < r:
m = l + r >> 1
if nums[m] < nums[r]: r = m
else: l = m + 1
return nums[l]