leetcode刷题类型（三） - - - 二分查找及其变种

  二分查找及其相关变形题目常用在有序数组中找指定值。通过将区间对半可以将时间复杂度降到O(log2N)
 

经典：在递增数组中寻找k值下标

  • 首先获取中间值，如果k值和中间值相等，那么中间值下标即为k值下标；
  • 如果k值小于中间值，则k值位置在左区间到中间值之间，将右区间修改为中间值；
  • 如果k值大于中间值，则k值位置在中间值到右区间之间，将左区间修改为中间值；
  • 直到中间值为k值，若左区间超过右区间，则说明整个数组没有k值，返回-1。
func binarySearch(arr []int,k int)int{
	left:=0
	right:=len(arr)-1
	mid:=0
	for left <= right {
		mid=left+(right-left)/2   //获取中间元素
		if arr[mid]==k {
			return mid
		}
		if arr[mid] < k {  //k值在右区间，即[mid+1,right]
			left=mid+1  //区间缩小一半
		}else{            //k值在左区间,即[left,mid-1]
			right=mid   //区间缩小一半
		}
	}
	return -1
}

 

69 Sqrt(x)

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

func mySqrt(x int) int {
	if x <= 1 {
		return x
	}
	left := 1
	right := x
	for left <= right {
		mid := left + (right-left)/2
		sqrt := x / mid //一个数 x 的开方 sqrt 一定在 0 ~ x 之间，并且满足 sqrt == x / sqrt
		if sqrt == mid {
			return mid
		}
		if sqrt < mid { //平方根在左区间，即[left,mid]
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return right   //循环退出时，right总是比left小1
}

 

744 寻找比目标字母大的最小字母

  给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。

  在比较时，字母是依序循环出现的。举个例子：如果目标字母 target = ‘z’ 并且字符列表为 letters = [‘a’, ‘b’]，则答案返回 ‘a’

func nextGreatestLetter(letters []byte, target byte) byte {
	left:=0
	right:=len(letters)-1    //若right=N,那么left=right=N时会数组越界

	for left<=right{
		mid:= left+(right-left)/2   
		if letters[mid] <= target {   //mid值比target小就右移
			left=mid+1
		}else{
			right=mid-1
		}
	}
	if left==0{   //右区间一直向左移动，直到到达左区间，说明第一个值就比target大
		return letters[0]
	}
	if left==len(letters){   //左区间一直向右移动，直到超过右区间，说明最后一个值也比target小
		return letters[0]
	}
	return letters[left]
}

 

540 有序数组中的单一元素

  给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。请你找出并返回只出现一次的那个数。

  仅对偶数索引进行二分查找，直到遇到与其后元素不相同的索引。

  • 如果mid的值和mid+1的值相同，则单个元素在mid之后
  • 如果mid的值和mid+1的值不同，则单个元素在mid之前
  • 如果mid的值和mid+1的值不同且和mid-1的值不通，则单个元素就是mid
func singleNonDuplicate(nums []int) int {
	left := 0
	right := len(nums) - 1

	for left < right { //left==right时，空间内只有一个元素，即查找的单个元素
		mid := left + (right-left)/2
		if mid%2 != 0 {
			mid-- //保证mid是偶数
		}
		if nums[mid] == nums[mid+1] { //单个元素在 mid 之后
			left = mid + 2 //因为mid和mid+1的值相同，所以区间改为[mid+2,right]
		} else {   //单个元素位于 mid，或者在 mid 之前
			if mid > 1 && nums[mid] != nums[mid-1] { //mid就是单个元素
				return nums[mid]
			}
			right = mid-2  //因为mid和mid-1的值相同，所以区间改为[left,mid-2]
		}
	}
	return nums[left]
}

 

278 第一个错误的版本

假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。

func firstBadVersion(n int) int {
	left := 1
	right := n
	mid := 0
	for left < right {
		mid = left + (right-left)/2
		if isBadVersion(mid) {
			right = mid //此时mid已经错误，那么mid左边的也可能已经错误
		} else {
			left = mid + 1 //此时mid还没有错误，那么第一个错误版本会在mid右边
		}
	}
	//此时left==right
	return left
}

 

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

  给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
  实际还是找有序数组的最小值

func findMin(nums []int) int {
	left := 0
	right := len(nums) - 1

	for left < right {
		mid := left + (right-left)/2
		if nums[mid] < nums[right] { //说明最小值在mid左区间
			right = mid
		} else {
			left = mid + 1 //nums[mid]已经比nums[right]大，说明最小值已经被旋转到mid之后
		}
	}
	//此时left==right
	return nums[left]
}
34 在排序数组中查找元素的第一个和最后一个位置

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

解法一：
  先用二分查找找到target的位置，然后分别向前向后找到不是target的值

func searchRange(nums []int, target int) []int {
	left:=0
	right:=len(nums)-1
	res:=make([]int,2)
	mid:=0
	for left <= right {
		mid=left+(right-left)/2
		if nums[mid] == target {
			break
		}
		if nums[mid] > target{   //target在mid左区间
			right=mid-1
		}else {
			left=mid+1
		}
	}
	//target在数组中，从mid向前后遍历直到遇到不是target的值
	if left <= right {
		for mid >=0 && nums[mid]==target{
			mid--
		}
		mid++
		res[0]=mid
		for mid <= len(nums)-1 && nums[mid]==target{
			mid++
		}
		res[1]=mid-1
		return res
	}
	//未命中，返回-1
	res[0]=-1
	res[1]=-1
	return res

}

解法二：
  可以用二分查找找出第一个位置和最后一个位置，但是寻找的方法有所不同，需要实现两个二分查找。我们将寻找 target 最后一个位置，转换成寻找 target+1 第一个位置，再往前移动一个位置。这样我们只需要实现一个二分查找代码即可。

func searchRange(nums []int, target int) []int {
	left := binarySearch(nums, target)
	right := binarySearch(nums, target+1) - 1
	if left == len(nums) || nums[left] != target {
		return []int{-1, -1}
	}
	if right < left {
		right = left
	}
	return []int{left, right}
}

func binarySearch(arr []int, k int) int {
	left := 0
	right := len(arr) ////不是(nums)-1，为了覆盖 target 大于 nums 最后一个元素的情况
	mid := 0
	for left < right {
		mid = left + (right-left)/2
		if arr[mid] >= k { //k值在右区间，即[mid+1,right]
			right = mid
		} else { //k值在左区间,即[left,mid-1]
			left = mid + 1
		}
	}
	return left
}

 
 
如有不对，烦请指出，感谢~
 
参考自：
http://www.cyc2018.xyz/
https://leetcode-cn.com/problems