文章目录

代码随想录之二分查找系列基础题目

1.二分查找

1.1暴力解法

func search(nums []int, target int) int {
if nums==nil {
       return -1
}
for i :=0; i<len(nums);i++{
    if  nums[i]==target{
        return i
    }
}
return -1
}

1.2左闭右闭区间二分查找

func search(nums []int, target int) int {
    high := len(nums)-1// 定义target在左闭右闭的区间里,[left, right]
    low := 0
    for low <= high {// 当left==right,区间[left, right]依然有效,所以用 <=
        mid := low + (high-low)/2   // 防止溢出 等同于(left + right)/2
        if nums[mid] == target { // 数组中找到目标值,直接返回下标
            return mid
        } else if nums[mid] > target {
            high = mid-1// target 在左区间,所以[left, middle - 1]
        } else {// target 在右区间,所以[middle + 1, right]
            low = mid+1
        }
    }
    return -1 // 未找到目标值
}
//可以debug尝试一下查[]int{1, 2, 3, 4, 7, 9, 10}中的3;正好low==high,mid右往右移动了
//注:不管是奇数个元素,还是偶数个元素,算的都是中间值
//可以debug尝试一下查[]int{1, 2, 3, 4, 7, 9, 10},寻找-1,最终high=-1,low=0,退出循环
可以debug尝试一下查[]int{1, 2, 3, 4, 7, 9, 10},寻找100,最终high=6,low=7,退出循环

image-20220205220821345

image-20220205220837364
在这里插入图片描述

1.3左闭右开区间二分查找

func search(nums []int, target int) int {
    high := len(nums)// 定义target在左闭右开的区间里,即:[left, right)
    low := 0
    for low < high {// 因为left == right的时候,在[left, right)是无效的空间,所以使用 <
        //假如数组长度有4个元素,则mid=1;则num是第二个元素
        //假如数组长度有5个元素,则mid=2;则num是第三个元素
        mid := low + (high-low)/2
        if nums[mid] == target { // 数组中找到目标值,直接返回下标
            return mid
        } else if nums[mid] > target {// target 在左区间,在[left, middle)中
            high = mid
        } else {// target 在右区间,在[middle + 1, right)中
            low = mid+1
        }
    }
    return -1// 未找到目标值
}
//可以debug尝试一下查[]int{1, 2, 3, 4, 7, 9, 10}中的3;正好low < high,差一点接近于low===high
//可以debug尝试一下查[]int{1, 2, 3, 4, 7, 9, 10},寻找-1,最终high=0,low=0,退出循环
可以debug尝试一下查[]int{1, 2, 3, 4, 7, 9, 10},寻找100,最终high=7,low=7,退出循环                                     

image-20220205220904873
在这里插入图片描述
在这里插入图片描述

1.4递归左闭右闭区间二分查找

func search(nums []int, target int) int {
   return  BinarySearch(nums,target,0,len(nums)-1)
}
func BinarySearch(array []int, target int, l, r int) int {
	if l > r {
		// 出界了,找不到
		return -1
	}
	// 从中间开始找
	mid := (l + r) / 2
	middleNum := array[mid]
	if middleNum == target {
		return mid // 找到了
	} else if middleNum > target {
		// 中间的数比目标还大,从左边找
		return BinarySearch(array, target, 0, mid-1)
	} else {
		// 中间的数比目标还小,从右边找
		return BinarySearch(array, target, mid+1, r)
	}
}

1.5递归左闭右开区间二分查找

func search(nums []int, target int) int {
   return  BinarySearch(nums,target,0,len(nums))
}
func BinarySearch(array []int, target int, l, r int) int {
	if l >= r {
		return -1
	}
	mid := (l + r) / 2
	middleNum := array[mid]
	if middleNum == target {
		return mid 
	} else if middleNum > target {
		return BinarySearch(array, target, 0, mid)
	} else {
		return BinarySearch(array, target, mid+1, r)
	}
}

704.二分查找

在这里插入图片描述

2.搜索插入位置

2.1暴力解法

func searchInsert(nums []int, target int) int {
   for i:=0;i<len(nums);i++{
    // 分别处理如下三种情况
        // 目标值在数组所有元素之前,返回0
        // 目标值等于数组中某一个元素
        // 目标值插入数组中的位置
       if target <= nums[i]{
           return i
       }
   }
   // 目标值在数组所有元素之后的情况
    return len(nums)// 如果target是最大的,或者 nums为空,则返回nums的长度
}
//时间复杂度:O(n)  空间复杂度:O(1)

image-20220205222147224
在这里插入图片描述

2.2左闭右闭区间二分查找

func searchInsert(nums []int, target int) int {
	left, right := 0, len(nums)-1// 定义target在左闭右闭的区间里,[left, right]
	for left <= right {// 当left==right,区间[left, right]依然有效
		mid := left + (right-left)/ 2  //也可以写成mid := left + (right-left) >> 1,防止溢出 等同于(left + right)/2
		if nums[mid] < target {
			left = mid + 1// target 在右区间,所以[middle + 1, right]
		} else if nums[mid] > target {
			right = mid -1 // target 在左区间,所以[left, middle - 1]
		} else {// nums[middle] == target
			return mid
		}
	}
	    // 分别处理如下四种情况
        // 目标值在数组所有元素之前  [0, -1]
        // 目标值等于数组中某一个元素  return middle;
        // 目标值插入数组中的位置 [left, right],return  right + 1
        // 目标值在数组所有元素之后的情况 [left, right], return right + 1
	return left
}
//时间复杂度:O(log n)
//空间复杂度:O(1)

二分法

image-20220205224122234
在这里插入图片描述
左闭右闭二分查找

在这里插入图片描述

2.3左闭右开区间二分查找

func searchInsert(nums []int, target int) int {
	left, right := 0, len(nums)// 定义target在左闭右开的区间里,[left, right)  target
	for left < right {// 因为left == right的时候,在[left, right)是无效的空间
		mid := left + (right-left)/ 2  //也可以写成mid := left + (right-left) >> 1
		if nums[mid] < target {// target 在右区间,在 [middle+1, right)中
			left = mid + 1
		} else if nums[mid] > target {
			right = mid // target 在左区间,在[left, middle)中
		} else {// nums[middle] == target
			return mid// 数组中找到目标值的情况,直接返回下标
		}
	}
	   // 分别处理如下四种情况
        // 目标值在数组所有元素之前 [0,0)
        // 目标值等于数组中某一个元素 return middle
        // 目标值插入数组中的位置 [left, right) ,return right 即可
        // 目标值在数组所有元素之后的情况 [left, right),return right 即可
	return left
}
//时间复杂度:O(log n)
//空间复杂度:O(1)

在这里插入图片描述
在这里插入图片描述

image-20220115124112401

image-20220205222842746

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

3.1左闭右闭区间二分查找

func searchRange(nums []int, target int) []int {
    return []int{searchFirst(nums, target), searchLast(nums, target)}
}

//寻找左边界
// 二分查找,寻找target的左边界leftBorder(不包括target)
// 如果leftBorder没有被赋值(即target在数组范围的右边,例如数组[3,3],target为4),为了处理情况一
func searchFirst(nums []int, target int) int {
	left, right := 0, len(nums)-1// 定义target在左闭右闭的区间里,[left, right]
	for left <= right {
		mid := left + (right-left)>>1
		if nums[mid] >= target {// 寻找左边界,就要在nums[middle] == target的时候更新right
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	if left == len(nums) || nums[left] != target { // 判断一下是否越界,或者不相等
		return -1
	}
	return left
}
//寻找右边界
// 二分查找,寻找target的右边界(不包括target)
// 如果rightBorder为没有被赋值(即target在数组范围的左边,例如数组[3,3],target为2),为了处理情况一
func searchLast(nums []int, target int) int {
	left, right := 0, len(nums)-1// 定义target在左闭右闭的区间里,[left, right]
	for left <= right {// 当left==right,区间[left, right]依然有效
		mid := left + (right-left)>>1
		if nums[mid] > target { // 这里是 > 而不是 >=
			right = mid - 1 // target 在左区间,所以[left, middle - 1]
		} else {// 当nums[middle] == target的时候,更新left,这样才能得到target的右边界
			left = mid + 1
		}
	}
	if right == -1 || nums[right] != target { // 判断一下是否越界,或者不相等
		return -1
	}
	return right // 这里返回 right 而不是 left
}

在这里插入图片描述
00

在这里插入图片描述

加粗样式

4.二分查找第一个元素

4.1左闭右闭区间二分查找

func main() {
	fmt.Println(searchFirst([]int{5, 7, 7, 8, 8, 10}, 1))  //输出-1;最终left=0,right=-1
	fmt.Println(searchFirst([]int{5, 7, 7, 8, 8, 10}, 8))  //输出3;最终left=3,right=2
	fmt.Println(searchFirst([]int{5, 7, 7, 8, 8, 10}, 19)) //输出-1;最终,left=6,right==5
	fmt.Println(searchFirst([]int{5, 7, 7, 8, 8, 10}, 6))  //输出-1;最终:left=1,right=0
	fmt.Println(searchFirst([]int{5, 7, 7, 8, 8, 10}, 5))  //输出0;最终:left=0,right=-1
}
func searchFirst(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		mid := left + (right-left)>>1
		if nums[mid] >= target {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	if left = len(nums) || nums[left] != target { // 判断一下是否越界,或者不相等
		return -1
	}
	return left
}

image-20220207093819476

image-20220207093839340

image.png

image-20220207093920154

5.二分查找第二个元素

5.1左闭右闭区间二分查找

func main() {
	fmt.Println(searchLast([]int{5, 7, 7, 8, 8, 10}, 1))  //输出-1,最终left==0,right=-1
	fmt.Println(searchLast([]int{5, 7, 7, 8, 8, 10}, 8))  //输出4,最终left=5,rught=4
	fmt.Println(searchLast([]int{5, 7, 7, 8, 8, 10}, 19)) //输出-1,最终left=6,right=5
    fmt.Println(searchLast([]int{5, 7, 7, 8, 8, 10}, 10)) //输出-1,最终left=6,right=5

	fmt.Println(searchLast([]int{5, 7, 7, 8, 8, 10}, 6))  //输出-1,left=1,right=0
	fmt.Println(searchLast([]int{5, 7, 7, 8, 8, 10}, 5))  //输出0,left=1,right=0
}
func searchLast(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		mid := left + (right-left)>>1
		if nums[mid] > target { // 这里是 > 而不是 >=
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	if right == -1 || nums[right] != target { // 判断一下是否越界,或者不相等
		return -1
	}
	return right // 这里返回 right 而不是 left
}

image-20220207094251658

6.剑指Offer04–二维数组中的查找

6.1暴力解法

func findNumberIn2DArray(matrix [][]int, target int) bool {
	if matrix == nil || len(matrix) == 0 || len(matrix[0]) == 0 {
		return false
	}
	rows := len(matrix)
	colums := len(matrix[0])
	for i := 0; i < rows; i++ {
		for j := 0; j < colums; j++ {
			if matrix[i][j] == target {
				return true
			}
		}
	}
	return false
}
//时间复杂度:O(nm)
//空间复杂度:O(1)

如果不考虑二维数组排好序的特点,则直接遍历整个二维数组的每一个元素,判断目标值是否在二维数组中存在。
依次遍历二维数组的每一行和每一列。如果找到一个元素等于目标值,则返回 true。如果遍历完毕仍未找到等于目标值的元素,则返回 false。

6.2左闭右闭区间二分查找


func searchMatrix2(matrix [][]int, target int) bool {
	var m = len(matrix)
	if m == 0 {
		return false
	}
	var n = len(matrix[0])
	var shortDim = min(m, n)
	for i := 0; i < shortDim; i++ {
		var rowFound = binarySearchRow(matrix, i, target)
		var colFount = binarySearchCol(matrix, i, target)
		if rowFound || colFount {
			return true
		}
	}
	return false
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

func binarySearchRow(matrix [][]int, row int, target int) bool {
	var left, right = row, len(matrix[0]) - 1
	for left <= right {
		var mid = left + (right - left) / 2
		if matrix[row][mid] == target {
			return true
		} else if matrix[row][mid] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return false
}

func binarySearchCol(matrix [][]int, col int, target int) bool {
	var left, right = col, len(matrix) - 1
	for left <= right {
		var mid = left + (right - left) / 2
		if matrix[mid][col] == target {
			return true
		} else if matrix[mid][col] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return false
}

在这里插入图片描述

6.3线性查找

func findNumberIn2DArray(matrix [][]int, target int) bool {
	i, j := len(matrix)-1, 0
	for i >= 0 && j < len(matrix[0]) {
		if target > matrix[i][j] {
			j++
		} else if target < matrix[i][j] {
			i--
		} else {
			return true
		}
	}
	return false
}

从左上角查会比较麻烦,直接从左下角比较轻松

在这里插入图片描述

在这里插入图片描述

7.搜索二维矩阵

7.1暴力解法

func searchMatrix(matrix [][]int, target int) bool {
if matrix == nil || len(matrix) == 0 || len(matrix[0]) == 0 {
		return false
	}
	rows := len(matrix)
	colums := len(matrix[0])
	for i := 0; i < rows; i++ {
		for j := 0; j < colums; j++ {
			if matrix[i][j] == target {
				return true
			}
		}
	}
	return false
}
//时间复杂度是 O(n^2)
//空间复杂度是 O(1)

7.2二分查找

func searchMatrix(matrix [][]int, target int) bool {
    var m, n = len(matrix), len(matrix[0])
    var left, right = 0, m * n - 1
    for left <= right {
     // mid 是一维数组的索引
        var mid = left + (right - left) / 2
         // mid / n 是将一维数组的索引转成二维数组的行坐标
        // mid % n 是将一维数组的索引转成二维数组的列坐标
        var num = matrix[mid / n][mid % n]
        if num == target {
            return true
        } else if num < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return false
}
//时间复杂度:O(logn)
//空间复杂度:O(1)

为了提高算法的效率,我们需要利用上给定矩阵的特点,也就是有序这个特点,如果我们将上面的二维矩阵转化成一维矩阵,你会发现这个一维矩阵是有序的,如下图:
做了这一层转换后,现在的问题就变成了:在一个排好序的数组中查找目标值是否存在,这个问题的最高效的解决方案是二分查找了。

在这里插入图片描述

74.搜索二维矩阵
在这里插入图片描述
在这里插入图片描述

8.搜索旋转排序数组

8.1暴力解法

func search(nums []int, target int) int {
for i :=0; i<len(nums);i++{
    if  nums[i]==target{
        return i
    }
}
return -1
}

8.2左闭右闭区间二分查找

func search(nums []int, target int) int {
if len(nums) == 0 {
		return -1
	}
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + (high-low)>>1
		// 先根据 nums[mid] 与 nums[low]、mid[high] 的关系判断 mid 是在左段还是右段 
		//然后再判断 target 是在 mid 的左边还是右边,从而调整左右边界 low和 right
		if nums[mid] == target {
			return mid
		} else if nums[mid] > nums[low] { // 在数值大的一部分区间里
			if nums[low] <= target && target < nums[mid] {
				high = mid - 1
			} else {
				low = mid + 1
			}
		} else if nums[mid] < nums[high] { // 在数值小的一部分区间里
			if nums[mid] < target && target <= nums[high] {
				low = mid + 1
			} else {
				high = mid - 1
			}
		} else {
			if nums[low] == nums[mid] {
				low++
			}
			if nums[high] == nums[mid] {
				high--
			}
		}
	}
	return -1
}
/*
时间复杂度:O(logn),其中 n为nums 数组的大小。整个算法时间复杂度即为二分查找的时间复杂度 O(logn)。
空间复杂度: O(1)。我们只需要常数级别的空间存放变量。
*/

对于有序数组,可以使用二分查找的方法查找元素。
但是这道题中,数组本身不是有序的,进行旋转后只保证了数组的局部是有序的,这还能进行二分查找吗?答案是可以的。
可以发现的是,我们将数组从中间分开成左右两部分的时候,一定有一部分的数组是有序的。拿示例来看,我们从 6 这个位置分开以后数组变成了 [4, 5, 6] 和 [7, 0, 1, 2] 两个部分,其中左边 [4, 5, 6] 这个部分的数组是有序的,其他也是如此。
这启示我们可以在常规二分查找的时候查看当前 mid 为分割位置分割出来的两个部分 [l, mid] 和 [mid + 1, r] 哪个部分是有序的,并根据有序的那个部分确定我们该如何改变二分查找的上下界,因为我们能够根据有序的那部分判断出 target 在不在这个部分:
1)如果 [l, mid - 1] 是有序数组,且 target 的大小满足[nums[l],nums[mid]],则我们应该将搜索范围缩小至 [l, mid - 1],否则在 [mid + 1, r] 中寻找。
2)如果 [mid, r] 是有序数组,且 target 的大小满足 [nums[mid+1],nums[r]],则我们应该将搜索范围缩小至 [mid + 1, r],否则在 [l, mid - 1] 中寻找。

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

9.搜索旋转排序数组II

9.1暴力解法

func search(nums []int, target int) bool {
for i :=0; i<len(nums);i++{
    if  nums[i]==target{
        return true
    }
}
return false
}

9.2左闭右闭区间二分查找

func search(nums []int, target int) bool {
	if len(nums) == 0 {
		return false
	}
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + (high-low)>>1
		if nums[mid] == target {
			return true
		} else if nums[mid] > nums[low] { 
			if nums[low] <= target && target < nums[mid] {
				high = mid - 1
			} else {
				low = mid + 1
			}
		} else if nums[mid] < nums[high] { 
			if nums[mid] < target && target <= nums[high] {
				low = mid + 1
			} else {
				high = mid - 1
			}
		} else {
			if nums[low] == nums[mid] {
				low++
			}
			if nums[high] == nums[mid] {
				high--
			}
		}
	}
	return false
}

这一题是第 33 题的加强版,实现代码完全一样,只不过输出变了。这一题输出 true 和 false 了。具体思路见第 33 题。

在这里插入图片描述
在这里插入图片描述

10.寻找旋转数组中的最小值

10.1暴力解法

func findMin(nums []int) int {
	min := nums[0]
	for _, num := range nums[1:] {
		if min > num {
			min = num
		}
	}
	return min
}

这一题也可以用暴力解法,从头开始遍历,动态维护一个最小值即可,时间复杂度 O(n)。

10.2巧用函数

func findMin(nums []int) int {
	sort.Ints(nums)
	return nums[0]
}

10.3左闭右闭区间二分查找解法一

//左闭右闭区间二分查找解法一
func findMin(nums []int) int {
    low, high := 0, len(nums) - 1
    for low < high {
        pivot := low + (high - low) / 2
        if nums[pivot] < nums[high] {//第一种情况
            high = pivot
        } else if nums[pivot] > nums[high]{
            low = pivot + 1
        }
    }
    return nums[low]
}
/*
时间复杂度:时间复杂度为 O(logn),其中 n 是数组nums 的长度。在二分查找的过程中,每一步会忽略一半的区间,因此时间复杂度为 O(logn)。
空间复杂度:O(1)。
*/

一个不包含重复元素的升序数组在经过旋转之后,可以得到下面可视化的折线图:
其中横轴表示数组元素的下标,纵轴表示数组元素的值。图中标出了最小值的位置,是我们需要查找的目标。
我们考虑寻转后的数组中的最后一个元素 x:在最小值右侧的元素(不包括最后一个元素本身),它们的值一定都严格小于 x;而在最小值左侧的元素,它们的值一定都严格大于 x。因此,我们可以根据这一条性质,通过二分查找的方法找出最小值。
在二分查找的每一步中,左边界为 low,右边界为 high,区间的中点为 pivot,最小值就在该区间内。
我们将中轴元素 nums[pivot] 与右边界元素nums[high] 进行比较,可能会有以下的三种情况:

第一种情况是nums[pivot]<nums[high]。如下图所示,这说明 nums[pivot] 是最小值右侧的元素,因此我们可以忽略二分查找区间的右半部分,可以收缩右边界:
即去掉最小值在[mid+1,high]的区域,因为mid可能是答案,所以让right=mid

          if nums[pivot] < nums[high] {//第二种情况
            high = pivot
            }

第二种情况是 nums[pivot]>nums[high]。如下图所示,这说明nums[pivot] 是最小值左侧的元素,因此我们可以忽略二分查找区间的左半部分。可以收缩左边界:
即去掉最小值在[left, mid]的区域, 因为mid一定不是最小值,所以left=mid+1

        if nums[pivot] > nums[high]{
            low = pivot + 1
        }

第三种情况:左值 > 中值, 中值 > 右值 :单调递减,无论如何旋转都不可能出现

在这里插入图片描述

结果:区间不断的缩减,直到left == right时跳出循环,剩下的最后一元素 nums[left]就是我们的最小值:

再分析一下for循环退出的条件:
1.如果输入数组只有一个数,左右边界位置重合,low == high,不会进入for循环,直接输出。
2.如果输入数组多于一个数,循环到最后,会只剩两个数,这里的位置low== mid == high - 1,即nums[low] == nums[mid]
1)如果nums[low] == nums[mid] < nums[high],则左边小、右边大,
会执行high = mid,使得low == high,左右边界位置重合,循环结束,nums[low]、nums[mid]、nums[high]都保存了最小值。
2)如果nums[low] == nums[mid] > nums[high],则左边大、右边小,
需要执行low = mid + 1,使得low == high,左右边界位置重合,循环结束,nums[low]与nums[high]都保存了最小值。

分析始终left <= mid,mid < right:
中间位置的计算:mid = left + (right - left) / 2
这里整数除法是向下取整的地板除,mid更靠近left,
再结合while循环的条件left < right,
可以知道left <= mid,mid < right,
即在while循环内,mid始终小于right。
因此在while循环内,nums[mid]要么大于要么小于nums[right],不会等于。

10.5左闭右闭区间二分查找解法一(优化版)

func findMin(nums []int) int {
  low, high := 0, len(nums) - 1
 if  nums[low] < nums[high] {
			return nums[low]
		}
    for low < high {
        //第一种情况
        if nums[low] < nums[high] {
			return nums[low]
		}
        pivot := low + (high - low) / 2
        if nums[pivot] < nums[high] {
            high = pivot
        } else if nums[pivot] > nums[high]{
            low = pivot + 1
        }
    }
    return nums[low]
}

再多增加一种情况,即第一种情况是左值 < 中值, 中值 < 右值 :没有旋转,最小值在最左边:

在这里插入图片描述

10.6左闭右闭区间二分查找解法二

// 解法二 二分
func findMin1(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	if len(nums) == 1 {
		return nums[0]
	}
	if nums[len(nums)-1] > nums[0] {
		return nums[0]
	}
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + (high-low)>>1
		if nums[low] < nums[high] {
			return nums[low]
		}
		if (mid == len(nums)-1 && nums[mid-1] > nums[mid]) || (mid < len(nums)-1 && mid > 0 && nums[mid-1] > nums[mid] && nums[mid] < nums[mid+1]) {
			return nums[mid]
		}
		if nums[mid] > nums[low] && nums[low] > nums[high] { // mid 在数值大的一部分区间里
			low = mid + 1
		} else if nums[mid] < nums[low] && nums[low] > nums[high] { // mid 在数值小的一部分区间里
			high = mid - 1
		} else {
			if nums[low] == nums[mid] {
				low++
			}
			if nums[high] == nums[mid] {
				high--
			}
		}
	}
	return -1
}

在这里插入图片描述
在这里插入图片描述

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

11.1暴力解法

func findMin(nums []int) int {
min := nums[0]
	for _, num := range nums[1:] {
		if min > num {
			min = num
		}
	}
	return min
}

11.2巧用函数

func findMin(nums []int) int {
	sort.Ints(nums)
	return nums[0]
}

11.3左闭右闭区间二分查找

func findMin(nums []int) int {
    low, high := 0, len(nums) - 1
    for low < high {
        pivot := low + (high - low) / 2
        if nums[pivot] < nums[high] {
            high = pivot
        } else if nums[pivot] > nums[high] {
            low = pivot + 1
        } else {
            high--
        }
    }
    return nums[low]
}
/*
时间复杂度:平均时间复杂度为 O(logn),其中 n 是数组nums 的长度。如果数组是随机生成的,那么数组中包含相同元素的概率很低,在二分查找的过程中,大部分情况都会忽略一半的区间。而在最坏情况下,如果数组中的元素完全相同,那么for循环就需要执行 n 次,每次忽略区间的右端点,时间复杂度为 O(n)。
空间复杂度:O(1)
*/

一个包含重复元素的升序数组在经过旋转之后,可以得到下面可视化的折线图:
其中横轴表示数组元素的下标,纵轴表示数组元素的值。图中标出了最小值的位置,是我们需要查找的目标。
我们考虑数组中的最后一个元素 x:在最小值右侧的元素,它们的值一定都小于等于 x;而在最小值左侧的元素,它们的值一定都大于等于x。因此,我们可以根据这一条性质,通过二分查找的方法找出最小值。
在二分查找的每一步中,左边界为 low,右边界为 high,区间的中点为 pivot,最小值就在该区间内。我们将中轴元素 nums[pivot] 与右边界元素 nums[high] 进行比较,可能会有以下的三种情况:

一种情况是nums[pivot]<nums[high]。如下图所示,这说明nums[pivot] 是最小值右侧的元素,因此我们可以忽略二分查找区间的右半部分。

第二种情况是 nums[pivot]>nums[high]。如下图所示,这说明 nums[pivot] 是最小值左侧的元素,因此我们可以忽略二分查找区间的左半部分

第三种情况是 nums[pivot]==nums[high]。如下图所示,由于重复元素的存在,我们并不能确定 nums[pivot] 究竟在最小值的左侧还是右侧,因此我们不能莽撞地忽略某一部分的元素。我们唯一可以知道的是,由于它们的值相同,所以无论 nums[high] 是不是最小值,都有一个它的「替代品」nums[pivot],因此我们可以忽略二分查找区间的右端点:

当二分查找结束时,我们就得到了最小值所在的位置。

在这里插入图片描述
在这里插入图片描述

12.剑指Offer11–旋转数组的最小数字

12.1左闭右闭区间二分查找

func minArray(numbers []int) int {
 low, high := 0, len(numbers) - 1
    for low < high {
        pivot := low + (high - low) / 2
        if numbers[pivot] < numbers[high] {
            high = pivot
        } else if numbers[pivot] > numbers[high] {
            low = pivot + 1
        } else {
            high--
        }
    }
    return numbers[low]
}

在这里插入图片描述

13.剑指Offer53 II–0~n-1中缺失的数字

13.1左闭右闭区间二分查找

func missingNumber(nums []int) int {
 high := len(nums)-1
    low := 0
    for low <= high {
        mid := low + (high-low)/2  
        if nums[mid] ==mid { 
            low=mid+1
        } else{
            high = mid-1
        }
    }
    return low
}
//时间复杂度O(logN): 二分法为对数级别复杂度。
//空间复杂度 O(1): 几个变量使用常数大小的额外空间。

排序数组中的搜索问题,首先想到 二分法 解决。
根据题意,数组可以按照以下规则划分为两部分。
左子数组:nums[i]=i ;
右子数组:nums[i] !=i ;
缺失的数字等于 “右子数组的首位元素” 对应的索引;因此考虑使用二分法查找 “右子数组的首位元素”

算法解析:
1.初始化: 左边界 i = 0 ,右边界 j = len(nums) - 1; 代表闭区间 [i,j] 。
2.循环二分: 当 i≤j 时循环 (即当闭区间 [i,j] 为空时跳出) ;
1)计算中点 m=(i+j)/2 ,其中 “/” 为向下取整除法;
2)若 nums[m]=m ,则 “右子数组的首位元素” 一定在闭区间 [m + 1, j][m+1,j] 中,因此执行 i = m + 1;
3)若 nums[m]!=m ,则 “左子数组的末位元素” 一定在闭区间 [i, m - 1] 中,因此执行 j=m−1;
返回值: 跳出时,变量 i 和 j 分别指向 “右子数组的首位元素” 和 “左子数组的末位元素” 。因此返回 i 即可。

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

14.剑指Offer53 I–在排序数组中查找数字I

14.1左闭右闭区间二分查找

func search(nums []int, target int) int {
    res1 :=searchLast(nums, target)
    res2 :=searchFirst(nums, target)
    if res1==-1{
        return 0
    }
    return res1-res2+1

}
//寻找左边界
// 二分查找,寻找target的左边界leftBorder(不包括target)
// 如果leftBorder没有被赋值(即target在数组范围的右边,例如数组[3,3],target为4),为了处理情况一
func searchFirst(nums []int, target int) int {
	left, right := 0, len(nums)-1// 定义target在左闭右闭的区间里,[left, right]
	for left <= right {
		mid := left + (right-left)>>1
		if nums[mid] >= target {// 寻找左边界,就要在nums[middle] == target的时候更新right
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	if left == len(nums) || nums[left] != target { // 判断一下是否越界,或者不相等
		return -1
	}
	return left
}
//寻找右边界
// 二分查找,寻找target的右边界(不包括target)
// 如果rightBorder为没有被赋值(即target在数组范围的左边,例如数组[3,3],target为2),为了处理情况一
func searchLast(nums []int, target int) int {
	left, right := 0, len(nums)-1// 定义target在左闭右闭的区间里,[left, right]
	for left <= right {// 当left==right,区间[left, right]依然有效
		mid := left + (right-left)>>1
		if nums[mid] > target { // 这里是 > 而不是 >=
			right = mid - 1 // target 在左区间,所以[left, middle - 1]
		} else {// 当nums[middle] == target的时候,更新left,这样才能得到target的右边界
			left = mid + 1
		}
	}
	if right == -1 || nums[right] != target { // 判断一下是否越界,或者不相等
		return -1
	}
	return right // 这里返回 right 而不是 left
}

在这里插入图片描述
在这里插入图片描述

15.x的平方根

15.1左闭右闭区间二分查找

func mySqrt(x int) int {
    l, h:= 1, x/2 + 1
    for l <= h {//这里不能写成l<h
        mid := l + (h - l) / 2
        if mid == x / mid {
            return mid
        } else if mid > x / mid {
            h = mid - 1
        } else {
            l = mid + 1
        }
    }

    return h
}
//时间复杂度:O(log x),即为二分查找需要的次数。
//空间复杂度:O(1)。

可以用二分查找的原因:
题目要求非负整数 x 的平方根,相当于 y = √x,由于这个函数是单调递增(有序)的,所以可以用二分查找进行求解。

细节思考:
1.比较 mid * mid 与 x 的大小,相等则返回 mid,否则去以 mid 为分割点将区间[0, x] 分成左右区间的两个区间中查找,直到不满足查找条件时退出。
2.由于非负整数 x(当 x ≠ 0 时) 的平方根一定是落在区间 [1, x/2 + 1],所以左右边界分别取 1 和 x/2 + 1,而不分别取 0 和 x,这样可缩小查找范围。
3.为了防止 mid * mid 太大而发生整型溢出,取 mid 跟 x / mid 进行比较。

说明:
右边界取 x / 2 + 1,不取 x / 2 的原因是 x / 2 会向下取整,使得 x / 2 = 0,此时左边界大于右边界,循环直接退出,导致出现 1 的平方根为 0 的错误。
当 x = 0 时,以上代码也适合。

补充说明:
如果最终没有出现 mid == x / mid 的情况,到底是 return right 还是 return left 呢?
1、可以通过调试得出;
2、循环结束的条件:left = right + 1,示例中提示了当 x = 8,其平方根是 2,类似于向下取整,循环退出时 left = 3, 所以应该返回 right。

进一步补充:
可能有些童鞋会问到,上面代码中循环的条件为何是 left <= right 而不是 left < right,其实这两个条件都可以,主要区别在于:
1.循环结束的条件不一样,前者是 left = right + 1,后者是 left = right,即前者当 left = right + 1 时,查找区间为空,后者当 left = right 时,查找区间为空。
2.右边界取值不一样,前者为 x / 2 + 1,后者可为 x / 2 + 2。
这里会提到一个循环不变量的概念:
循环不变量:
1.初始化:它在循环的第一轮迭代开始之前,应该是正确的。
2.如果在循环的某一次迭代开始之前它是正确的,那么,在下一次迭代开始之前,它也应该保持正确。
3.当循环结束时,不变式给了我们一个有用的性质,它有助于表明算法是正确的。
本题循环条件可以是 left <= right 也可以是 left < right,关键是查找过程中始终要维护查找区间 [left, right] 或 [left, right)。

15.2左闭右开区间二分查找

func mySqrt(x int) int {
    l, h:= 1, x/2 + 2
        //  循环不变量 始终维持在区间 [left, right) 中查找,当 left = right 时,区间为空,查找结束
    for l < h {
        mid := l + (h - l) / 2
        if mid == x / mid {
            return mid   //  mid 等于 √x ,代表查找到 target,则直接返回
        } else if mid > x / mid {     //  mid 大于 √x ,在 mid 前半区间 [left, mid) 中查找
            h = mid 
        } else {
            l = mid + 1  //  mid 小于 √x ,在 mid 后半区间 [mid + 1, right) 中查找
        }
    }

    return h-1
}

补充一个循环条件为 left < right 的 代码。
最后返回的是 right - 1,这是因为:
定义的查找区间是左闭右开,取不到右边界;当 left == right 时,循环退出,由于 right 取不到,而且平方根有点向下取整的意味,所以取 right - 1;

在这里插入图片描述