二分搜索

type

status

date

slug

summary

二分搜索算法适用于有序数组。如果按照暴力搜索算法，那么需要从头到尾遍历数组元素，时间复杂度为，而如果使用二分搜索，那么其时间复杂度为，根据时间复杂度曲线图可知，二分搜索的算法效率要优于线性查找。

二叉查找的实质其实就是将有序数组转化为一个二叉搜索树：

每一次搜索其实就是从二叉树的根节点开始向下搜索，如果目标值大于当前节点，则搜索右子树，如果目标值小于当前节点，则搜索左子树，直到搜索到叶子节点为止。所以二分搜索的时间复杂度其实就是有序数组转化为二叉搜索树后的高度。

非递归版本

递归版本

二分搜索题目

搜索插入位置

题目：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。

示例:

在排序数组中查找元素的第一个和最后一个位置

题目：给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。

示例：

寻找峰值

题目：峰值元素是指其值严格大于左右相邻值的元素。给一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。可以假设nums[-1] = nums[n] = -∞ 。必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例：

如果把数组看做是高低不平的一条路，找峰值其实就是找小山坡。我们处在任意一点时，只要往左右两边更高的地方走就一定能到小山坡，因为nums[-1] = nums[n] = -∞这个条件其实就是说路的尽头必然是下坡路，所以往上坡走要嘛提前遇到下坡，要嘛在路尽头遇到下坡。当我们确定一个方向后就可以舍弃掉另一个方向了。

令中间的下标为mid，有四种情况分别讨论：

nums[mid-1] < nums[mid] > nums[mid+1]，这时，nums[mid]即为峰值，返回mid就行

nums[mid-1] < nums[mid] < nums[mid+1] 先假设mid右边没有峰值，那么，nums[mid+2]必须大于nums[mid+1]，否则nums[mid+1]就是峰值了同样的道理，nums[mid+3] 必须大于 nums[mid+2]，一直这样下去推到最大的下标right时， nums[right]必然为峰值，因为前面保证了nums[right-1] < nums[right] 这与假设矛盾，所以mid右边必然有峰值，于是可以安心的舍弃mid左边的数组了

nums[mid-1] > nums[mid] > nums[mid+1] 其实与情况2的方法一样，可以通过反证法证明，左边必然有峰值

nums[mid-1] > nums[mid] < nums[mid+1] 与情况3没有区别

搜索二维矩阵

题目：编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。

每行的第一个整数大于前一行的最后一个整数。

示例：

搜索二维矩阵II

题目：编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。

每列的元素从上到下升序排列。

示例：

由于矩阵中每一行的元素都是升序排列的，因此可以对每一行都使用一次二分查找，判断是否在该行中，从而判断是否出现。

寻找旋转排序数组中的最小值

题目：已知一个长度为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) 的算法解决此问题。

示例：

寻找最小的元素只存在三种情况：

数组旋转后的顺序没有变化

这种情况下nums[L] <= nums[M] <= nums[R]，最小值为nums[L]

数组旋转后最小值在索引M的右侧

这种情况下nums[L] <= nums[M] >= nums[R]，[L,M]为升序，最小值只能在M的右边，故更改左边界L=M+1

数组旋转后最小值在索引M的左侧

这种情况下nums[L] >= nums[M]，nums[R] >= nums[M], [M,R]为升序，最小值只能在M的左边(包含M)，故更改右边界R=M

寻找旋转排序数组中的最小值II

题目：给一个可能存在重复元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请找出并返回数组中的 最小元素 。必须尽可能减少整个过程的操作步骤。

示例：

搜索旋转排序数组

题目：

整数数组 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 。必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例：

初始化L=0，R=right，M=(L+R)/2，target=0。针对区间[L,M)和(M,R]为升序区间两种情况分别讨论：

[L,M)为升序区间

这个时候target如果在升序区间[L,M)范围，后面就只需在升序区间查找R=M-1。否则L=M+1。

(M,R]为升序区间

这个时候target如果在升序区间(M,R]范围，后面就只需在升序区间查找L=M+1。否则R=M-1。

寻找重复数

题目：给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例：

由于数组中存储的数的范围是[1,n]且是连续的，所以可以进行二分查找，遍历数组统计小于等于数组中整数范围的中点mid的个数cnt：

如果cnt > mid则重复的数一定在mid左边

否则一定在mid的右边

然后区间对半缩小，直到l > h时，l即为重复的数

x的平方根

题目：给你一个非负整数 x ，计算并返回 x 的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去。

示例：

Pow(x, n)

题目：实现 pow(x,n)，即计算x的整数n次幂函数

示例：

快速幂解析

，令为整数，则需要分为奇偶两种情况（设向下取整除法符号为 "//"）:

当为奇数时，二分后会多出一项

幂结果获取：

根据推导，可通过循环操作，每次把幂从降至，直至将幂降为0

设，则初始状态。在循环二分时，每当为奇数时，将多出的一项乘入，则最终可化至，返回即可

转化为位运算：

向下整除等价于右移一位

取余数等价于判断二进制最右位

猜数字

猜数字游戏的规则如下：

每轮游戏，我都会从 1 到 n 随机选择一个数字。请你猜选出的是哪个数字。

如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。

你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：

1：我选出的数字比你猜的数字小 pick < num

1：我选出的数字比你猜的数字大 pick > num

0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num

返回我选出的数字。