解释

二分查找也常被称为二分法或者折半查找，每次查找时通过将待查找区间分成两部分并只取 一部分继续查找，将查找的复杂度大大减少。对于一个长度为 O(n) 的数组，二分查找的时间复 杂度为 O(log n)。

举例来说，给定一个排好序的数组 {3,4,5,6,7}，我们希望查找 4 在不在这个数组内。第一次 折半时考虑中位数 5，因为 5 大于 4, 所以如果 4 存在于这个数组，那么其必定存在于 5 左边这一 半。于是我们的查找区间变成了 {3,4,5}。（注意，根据具体情况和您的刷题习惯，这里的 5 可以 保留也可以不保留，并不影响时间复杂度的级别。）第二次折半时考虑新的中位数 4，正好是我们 需要查找的数字。于是我们发现，对于一个长度为 5 的数组，我们只进行了 2 次查找。如果是遍 历数组，最坏的情况则需要查找 5 次。

我们也可以用更加数学的方式定义二分查找。给定一个在 [a, b] 区间内的单调函数 f (x)，若 f (a) 和 f (b) 正负性相反，那么必定存在一个解 c，使得 f (c) = 0。在上个例子中，f (x) 是离散函数 f (x) = x +2，查找 4 是否存在等价于求 f (x) −4 = 0 是否有离散解。因为 f (1) −4 = 3−4 = −1 < 0、 f (5) − 4 = 7 − 4 = 3 > 0，且函数在区间内单调递增，因此我们可以利用二分查找求解。如果最后 二分到了不能再分的情况，如只剩一个数字，且剩余区间里不存在满足条件的解，则说明不存在 离散解，即 4 不在这个数组内。

具体到代码上，二分查找时区间的左右端取开区间还是闭区间在绝大多数时候都可以，因此 有些初学者会容易搞不清楚如何定义区间开闭性。这里我提供两个小诀窍，第一是尝试熟练使用 一种写法，比如左闭右开（满足 C++、Python 等语言的习惯）或左闭右闭（便于处理边界条件）， 尽量只保持这一种写法；第二是在刷题时思考如果最后区间只剩下一个数或者两个数，自己的写 法是否会陷入死循环，如果某种写法无法跳出死循环，则考虑尝试另一种写法。

二分查找也可以看作双指针的一种特殊情况，但我们一般会将二者区分。双指针类型的题， 指针通常是一步一步移动的，而在二分查找里，指针每次移动半个区间长度。

求开方

X的平方根

根号 x 的取值范围一定在 [0,x] 之间，这个区间内的值是递增有序的，有边界的，可以用下标访问的，满足这三点正好也就满足了二分搜索的 3 大条件。所以解题思路一，二分搜索。

还有一个叫牛顿迭代法的东西，代码参考下面

// 解法二 牛顿迭代法 https://en.wikipedia.org/wiki/Integer_square_root
func mySqrt1(x int) int {
	r := x
	for r*r > x {
		r = (r + x/r) / 2
	}
	return r
}

func mySqrt(x int) int {
	if x == 0 {
		return 0
	}
	// 定义一个left和right两个指针，以及最后的答案
	left, right, res := 1, x, 0
	for left <= right {
		// 右移一位相当于除2操作，右移n位相当于除以2的n次方
		// 我们这里修改一下right
		// 我们这里相当于求解 f (x) = x^2 − a = 0
		// 这里这样做可以让我们的值更加平均
		mid := left + ((right - left) >> 1)
		// 小于时我们移动left指针，同时记录当前结果
		// 我们的结果一般都是使用左指针来
		if mid < x/mid {
			left = mid + 1
			res = mid
		} else if mid == x/mid {
			return mid
		} else {
			right = mid - 1
		}
	}
	return res
}

查找区间

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

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

解法一我们可以使用双指针来进行解题，像这种数组并且数组有序的题目，第一个想到的就应该是双指针，通过两个指针可以非常方便的进行双向遍历操作

// 解法1 使用双指针
func searchRange(nums []int, target int) []int {
	if len(nums) ==0{
		return []int{-1,-1}
	}
	// 使用双指针
	low,high:=0,len(nums)-1
	// 当low大于high时我们就可以跳循环了
	for low < high {
		// 当high指针不为target时，我们的high指针--
		if nums[high] != target {
			high --
		}
		// 当low指针不为target时，我们的low指针++,这里我们需要同时判断
		if nums[low] != target {
			low ++
		}
		// 当两个指针都为target时我们就跳出循环
		if nums[high] == target && nums[low] == target {
			break
		}
	}
	// 只要有一个不是target那么就说明结果错误，我们就让两个指针同时为-1
	if nums[high] != target {
		high = -1
		low = -1
	}
	return []int{low,high}
}

大佬用的是二分查找的方法，分别查找出第一次出现的位置和最后一次出现的位置，然后在返回

这里我们要理解一下high = mid，因为我们是满足条件的情况，这个时候high其实就已经满足条件了，我们这里只需要让high为mid，后面当low等于high时我们就退出循环，此时low就是mid

func searchRange(nums []int, target int) []int {
	if len(nums) ==0{
		return []int{-1,-1}
	}
	low:=findLeft(nums,target)
	high:=findRight(nums,target)
	if low==len(nums) || nums[low]!= target {
		return []int{-1,-1}
	} else {
		return []int{low,high}
	}

}
// 找出第一次出现的位置
func findLeft(nums []int,target int) int {
	// 这里我们使用左闭右开的写法
	low,high,mid:=0,len(nums),0
	// 这里我们开始遍历
	for low < high {
		mid = (low+high) / 2
		// 关键部分在这里，为什么我们可以找到第一次出现的位置呢
		// 因为当我们的结果等于target时，我们就已经找到了
		// 这里我们让high等于mid，是因为我们的high就是正确答案，所以我们不能mid-1
		if nums[mid] >= target {
			high = mid
		} else {
			low = mid + 1
		}
	}
	return low
}
// 找出最后一次出现的位置
func findRight(nums []int,target int) int {
	low,high,mid:=0,len(nums),0
	// 这里我们开始遍历
	for low < high {
		mid = (low+high) / 2
		// 关键部分在这里，为什么我们可以找到第一次出现的位置呢
		// 因为当我们的结果大于target时，我们就相当于是找了了最后一次出现位置的后一位
		if nums[mid] > target {
			high = mid
		} else {
			low = mid + 1
		}
	}
	return low-1
}

旋转数组查找数字

搜索选择排序数组

81. 搜索旋转排序数组 II - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

这题目利用了我们数组旋转后我们的数组依旧会有两段是有序的，然后当我们进行二分查找时，我们可以先判断mid和high的关系，如果mid小于high，那么就说明mid和high这段是有序的反之（反正每次左右两部分至少有一部分是有序的这个性质很重要）然后我们可以通过target >= nums[low] && target < nums[mid] 这个种判断来确保我们没有漏选

func search(nums []int, target int) bool {
	low,high:=0,len(nums)-1
	// 这里为什么要low等于high呢，因为我们当low等于high时我们还需要判断一下，确保没有漏掉值
	for low<=high {
		// 求中点
		mid:=(low+high)/2
		// 当我们找到时，直接返回
		if nums[mid] == target {
			return true
		} else if nums[low] == nums[mid] {
			// 当low和mid相等时，我们就尝试移动low，再判断一下
			low ++
		} else if nums[mid] <= nums[high]{
			// 当mid小于或等于high时，说明当前这个区间是递增的
			// 这里有两个细节，一个是我们计算时要确保target大于nums[mid]
			// 然后target小于等于nums[high](当等于时我们就必须移动low指针)
			if target > nums[mid] && target <= nums[high] {
				low = mid + 1
			} else {
				high = mid - 1
			}
		} else {
			// 然后这里就是nums[mid] > nums[high]的情况了
			if target >= nums[low] && target < nums[mid] {
				high = mid - 1
			} else {
				low = mid + 1
			}
		}
	}
	return false
}

基础难度 154. Find Minimum in Rotated Sorted Array II (Medium) 旋转数组的变形题之一。 540. Single Element in a Sorted Array (Medium) 在出现独立数之前和之后，奇偶位数的值发生了什么变化？ 进阶难度 4. Median of Two Sorted Arrays (Hard) 需要对两个数组同时进行二分搜索。