Binary Search

Binary Search #

  • 二分搜索的经典写法。需要注意的三点:
    1. 循环退出条件,注意是 low <= high,而不是 low < high。
    2. mid 的取值,mid := low + (high-low)»1
    3. low 和 high 的更新。low = mid + 1,high = mid - 1。
func binarySearchMatrix(nums []int, target int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + (high-low)>>1
		if nums[mid] == target {
			return mid
		} else if nums[mid] > target {
			high = mid - 1
		} else {
			low = mid + 1
		}
	}
	return -1
}
  • 二分搜索的变种写法。有 4 个基本变种:
    1. 查找第一个与 target 相等的元素,时间复杂度 O(logn)
    2. 查找最后一个与 target 相等的元素,时间复杂度 O(logn)
    3. 查找第一个大于等于 target 的元素,时间复杂度 O(logn)
    4. 查找最后一个小于等于 target 的元素,时间复杂度 O(logn)
// 二分查找第一个与 target 相等的元素,时间复杂度 O(logn)
func searchFirstEqualElement(nums []int, target int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + ((high - low) >> 1)
		if nums[mid] > target {
			high = mid - 1
		} else if nums[mid] < target {
			low = mid + 1
		} else {
			if (mid == 0) || (nums[mid-1] != target) { // 找到第一个与 target 相等的元素
				return mid
			}
			high = mid - 1
		}
	}
	return -1
}

// 二分查找最后一个与 target 相等的元素,时间复杂度 O(logn)
func searchLastEqualElement(nums []int, target int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + ((high - low) >> 1)
		if nums[mid] > target {
			high = mid - 1
		} else if nums[mid] < target {
			low = mid + 1
		} else {
			if (mid == len(nums)-1) || (nums[mid+1] != target) { // 找到最后一个与 target 相等的元素
				return mid
			}
			low = mid + 1
		}
	}
	return -1
}

// 二分查找第一个大于等于 target 的元素,时间复杂度 O(logn)
func searchFirstGreaterElement(nums []int, target int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + ((high - low) >> 1)
		if nums[mid] >= target {
			if (mid == 0) || (nums[mid-1] < target) { // 找到第一个大于等于 target 的元素
				return mid
			}
			high = mid - 1
		} else {
			low = mid + 1
		}
	}
	return -1
}

// 二分查找最后一个小于等于 target 的元素,时间复杂度 O(logn)
func searchLastLessElement(nums []int, target int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + ((high - low) >> 1)
		if nums[mid] <= target {
			if (mid == len(nums)-1) || (nums[mid+1] > target) { // 找到最后一个小于等于 target 的元素
				return mid
			}
			low = mid + 1
		} else {
			high = mid - 1
		}
	}
	return -1
}
  • 在基本有序的数组中用二分搜索。经典解法可以解,变种写法也可以写,常见的题型,在山峰数组中找山峰,在旋转有序数组中找分界点。第 33 题,第 81 题,第 153 题,第 154 题,第 162 题,第 852 题
func peakIndexInMountainArray(A []int) int {
	low, high := 0, len(A)-1
	for low < high {
		mid := low + (high-low)>>1
		// 如果 mid 较大,则左侧存在峰值,high = m,如果 mid + 1 较大,则右侧存在峰值,low = mid + 1
		if A[mid] > A[mid+1] {
			high = mid
		} else {
			low = mid + 1
		}
	}
	return low
}
  • max-min 最大值最小化问题。求在最小满足条件的情况下的最大值。第 410 题,第 875 题,第 1011 题,第 1283 题。
TitleSolutionDifficultyTimeSpace收藏
50. Pow(x, n)GoMediumO(log n)O(1)
69. Sqrt(x)GoEasyO(log n)O(1)
167. Two Sum II - Input array is sortedGoEasyO(n)O(1)
209. Minimum Size Subarray SumGoMediumO(n)O(1)
222. Count Complete Tree NodesGoMediumO(n)O(1)
230. Kth Smallest Element in a BSTGoMediumO(n)O(1)
287. Find the Duplicate NumberGoEasyO(n)O(1)❤️
300. Longest Increasing SubsequenceGoMediumO(n log n)O(n)
349. Intersection of Two ArraysGoEasyO(n)O(n)
350. Intersection of Two Arrays IIGoEasyO(n)O(n)
392. Is SubsequenceGoMediumO(n)O(1)
454. 4Sum IIGoMediumO(n^2)O(n)
710. Random Pick with BlacklistGoHardO(n)O(n)
———————————————–———————————————————–———————–———–——–

⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者