2.11 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 题。
No.TitleSolutionDifficultyTimeComplexitySpaceComplexityFavoriteAcceptance
0004Median of Two Sorted ArraysGoHard36.2%
0033Search in Rotated Sorted ArrayGoMedium39.0%
0034Find First and Last Position of Element in Sorted ArrayGoMedium41.9%
0035Search Insert PositionGoEasy43.4%
0069Sqrt(x)GoEasyO(log n)O(1)37.4%
0074Search a 2D MatrixGoMedium47.7%
0081Search in Rotated Sorted Array IIGoMedium35.7%
0153Find Minimum in Rotated Sorted ArrayGoMedium48.9%
0154Find Minimum in Rotated Sorted Array IIGoHard43.5%
0162Find Peak ElementGoMedium46.0%
0167Two Sum II - Input Array Is SortedGoMediumO(n)O(1)60.0%
0209Minimum Size Subarray SumGoMediumO(n)O(1)45.0%
0222Count Complete Tree NodesGoMediumO(n)O(1)60.6%
0240Search a 2D Matrix IIGoMedium51.0%
0268Missing NumberGoEasy62.6%
0275H-Index IIGoMedium37.5%
0278First Bad VersionGoEasy43.3%
0287Find the Duplicate NumberGoMediumO(n)O(1)❤️59.1%
0300Longest Increasing SubsequenceGoMediumO(n log n)O(n)52.2%
0315Count of Smaller Numbers After SelfGoHard42.6%
0327Count of Range SumGoHard35.8%
0349Intersection of Two ArraysGoEasyO(n)O(n)70.9%
0350Intersection of Two Arrays IIGoEasyO(n)O(n)56.0%
0352Data Stream as Disjoint IntervalsGoHard59.7%
0354Russian Doll EnvelopesGoHard37.9%
0367Valid Perfect SquareGoEasy43.3%
0374Guess Number Higher or LowerGoEasy51.9%
0378Kth Smallest Element in a Sorted MatrixGoMedium61.8%
0400Nth DigitGoMedium34.1%
0410Split Array Largest SumGoHard53.5%
0436Find Right IntervalGoMedium50.8%
0441Arranging CoinsGoEasy46.2%
0456132 PatternGoMedium32.4%
0475HeatersGoMedium36.5%
0483Smallest Good BaseGoHard38.8%
0493Reverse PairsGoHard30.9%
0497Random Point in Non-overlapping RectanglesGoMedium39.4%
0528Random Pick with WeightGoMedium46.1%
0532K-diff Pairs in an ArrayGoMedium41.2%
0540Single Element in a Sorted ArrayGoMedium59.1%
0611Valid Triangle NumberGoMedium50.6%
0633Sum of Square NumbersGoMedium34.4%
0658Find K Closest ElementsGoMedium46.8%
0668Kth Smallest Number in Multiplication TableGoHard51.4%
0704Binary SearchGoEasy56.1%
0710Random Pick with BlacklistGoHardO(n)O(n)33.5%
0718Maximum Length of Repeated SubarrayGoMedium51.3%
0719Find K-th Smallest Pair DistanceGoHard36.7%
0729My Calendar IGoMedium56.8%
0732My Calendar IIIGoHard71.5%
0744Find Smallest Letter Greater Than TargetGoEasy45.8%
0778Swim in Rising WaterGoHard59.8%
0786K-th Smallest Prime FractionGoMedium51.7%
0793Preimage Size of Factorial Zeroes FunctionGoHard43.2%
0825Friends Of Appropriate AgesGoMedium46.3%
0826Most Profit Assigning WorkGoMedium44.9%
0852Peak Index in a Mountain ArrayGoMedium69.0%
0862Shortest Subarray with Sum at Least KGoHard26.0%
0875Koko Eating BananasGoMedium52.1%
0878Nth Magical NumberGoHard35.4%
0887Super Egg DropGoHard27.1%
0888Fair Candy SwapGoEasy60.7%
0911Online ElectionGoMedium52.2%
0981Time Based Key-Value StoreGoMedium52.2%
1004Max Consecutive Ones IIIGoMedium63.2%
1011Capacity To Ship Packages Within D DaysGoMedium67.7%
1157Online Majority Element In SubarrayGoHard41.8%
1170Compare Strings by Frequency of the Smallest CharacterGoMedium61.5%
1201Ugly Number IIIGoMedium28.9%
1208Get Equal Substrings Within BudgetGoMedium48.6%
1235Maximum Profit in Job SchedulingGoHard53.4%
1283Find the Smallest Divisor Given a ThresholdGoMedium56.2%
1300Sum of Mutated Array Closest to TargetGoMedium43.6%
1337The K Weakest Rows in a MatrixGoEasy72.1%
1385Find the Distance Value Between Two ArraysGoEasy66.6%
1439Find the Kth Smallest Sum of a Matrix With Sorted RowsGoHard61.4%
1482Minimum Number of Days to Make m BouquetsGoMedium54.0%
1539Kth Missing Positive NumberGoEasy58.6%
1608Special Array With X Elements Greater Than or Equal XGoEasy60.5%
1631Path With Minimum EffortGoMedium55.7%
1648Sell Diminishing-Valued Colored BallsGoMedium30.4%
1649Create Sorted Array through InstructionsGoHard37.5%
1658Minimum Operations to Reduce X to ZeroGoMedium37.6%
1818Minimum Absolute Sum DifferenceGoMedium30.4%
——————————————————————-——-—————-—————————-————-————-

⬅️上一页

下一页➡️

Calendar Apr 8, 2023
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者