二分法

二分法使用场景：前提是排好序的数组，看到排好序的应该有使用二分法的想法。使用的时候，要知道二分法的作用是可以更快速的找出符合条件的值。时间复杂度为$On^2$，而全局遍历会使用$On$的时间

二分法使用方法：三个变量决定一切。x，y，mid 分别表示数组的左边界、右边界、中间值。使用中间值，来计算下一次遍历的数组是左子数组还是右子数组。

如下图：

我们知道了二分法的使用场景之后，看一个例子(注：本文代码均为Golang语言)

一、题目描述

LeetCode-53.0~n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例 1:

输入: [0,1,3]
输出: 2
示例 2:

输入: [0,1,2,3,4,5,6,7,9]
输出: 8

二、思路分析

分析：数组是有序数列，考虑使用二分法。

怎么使用：首先分析题目，下标与对应的值应一致，第一个不一致的值就是我们要找的值。怎么找不一致的值，我们可以把数组一分为二去寻找。

三、AC代码

 func missingNumber(nums []int) int {
	lenNum := len(nums)
	var i, j, m int
	j = lenNum - 1
	for i <= j {
		if nums[0] != 0 {  // 特殊值
			return 0
		}
		m = (i + j) / 2  // 取中间值
		if nums[m] == m { // 若中间值==其下标 说明数组的左部分是OK的，那么不一致的值就在右部分
			i = m + 1 // i的值变更
		} else { // 若中间值!=其下标 说明数组的左部分出现了不一致的情况，开始遍历左部分
			j = m - 1 // j的值变更
		}
	}
	return i
}

四、总结

本题为easy难度，其实从一个简单的题目可以能感觉出二分法的意义。不如，再练中等题目试一试

同系列题目

• LeetCode-275.H指数【难度：中等】

示例:

输入: citations = [0,1,3,5,6]
输出: 3
解释: 给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 0, 1, 3, 5, 6 次。
由于研究者有 3 篇论文每篇至少被引用了 3 次，其余两篇论文每篇被引用不多于 3 次，所以她的 h 指数是 3。

提示：

设定 h=n-i对应被应用的文章数，a[i]对应的是引用次数。
则h <= a[i]
也即 n-i <= a[i]

func hIndex(citations []int) int {
	lenCi := len(citations)
	var i, j, mid, ans int
	j = lenCi - 1
	for i <= j {
		mid = (i + j) / 2
		h := lenCi - mid
		if h <= citations[mid] {
			ans = h
			j = mid - 1
		} else {
			i = mid + 1
		}
	}
	return ans
}

• LeetCode-540.有序数组中的单一元素【难度：中等】

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

示例 1:

输入: [1,1,2,3,3,4,4,8,8]
输出: 2
示例 2:

输入: [3,3,7,7,10,11,11]
输出: 10

AC代码

func singleNonDuplicate(nums []int) int {
	lenN := len(nums)
	var i, j, mid int
	j = lenN - 1
	for i < j {
		mid = (i + j) / 2
		if mid%2 == 0 { // 一分为二后的元素是偶数个
			if nums[mid] == nums[mid-1] { // 
				j = mid - 2
			} else if nums[mid] == nums[mid+1] {
				i = mid + 2
			} else { // 中间值即为单一元素
				return nums[mid]
			}
		} else { // 一分为二后的元素是奇数个
			if nums[mid] == nums[mid-1] {
				i = mid + 1
			} else if nums[mid] == nums[mid+1] {
				j = mid - 1
			} else {
				return nums[mid]
			}
		}
	}
	return nums[i]
}

赏

感谢您的认可

支付宝