做旅游攻略网站好,苏州企业网站推广,长沙关键词优化服务,网店美工素材我们知道二分查找算法。二分查找是最容易正确的算法。我提出了一些我在二分搜索中收集的有趣问题。有一些关于二分搜索的请求。我请求您遵守准则#xff1a;“我真诚地尝试解决问题并确保不存在极端情况”。阅读完每个问题后#xff0c;最小化浏览器并尝试解决它。 … 我们知道二分查找算法。二分查找是最容易正确的算法。我提出了一些我在二分搜索中收集的有趣问题。有一些关于二分搜索的请求。我请求您遵守准则“我真诚地尝试解决问题并确保不存在极端情况”。阅读完每个问题后最小化浏览器并尝试解决它。 问题陈述给定一个由 N 个不同元素组成的排序数组使用最少的比较次数在数组中找到一个键。 您认为二分搜索是在排序数组中搜索键的最佳选择吗无需太多理论这里是典型的二分搜索算法。
# Returns location of key, or -1 if not found def BinarySearch(A, l, r, key): while (l r): m l (r - l) // 2 if A[m] key: #first comparison return m if A[m] key: # second comparison l m 1 else: r m - 1 return -1 This code is contributed by Rajat Kumar 理论上最坏情况下我们需要进行log N 1次比较。如果我们观察的话我们会在每次迭代中使用两次比较除非最终成功匹配如果有。在实践中比较将是昂贵的操作它不仅仅是原始类型比较。尽量减少与理论极限的比较更为经济。请参阅下图了解下一个实现中索引的初始化。 以下实现使用较少的比较次数。
# Invariant: A[l] key and A[r] key # Boundary: |r - l| 1 # Input: A[l .... r-1] def BinarySearch(A, l, r, key): while (r-l 1): m l(r-l)//2 if A[m] key: l m else: r m if A[l] key: return l if A[r] key: return r return -1 Code is written by Rajat Kumar 在 while 循环中我们仅依赖于一次比较。搜索空间收敛到将l和r指向两个不同的连续元素。我们需要再进行一次比较来跟踪搜索状态。您可以查看示例测试用例 http://ideone.com/76bad0。 C11 代码。 问题陈述给定一个由 N 个不同整数组成的数组找到输入“key”的下限值。假设 A {-1, 2, 3, 5, 6, 8, 9, 10} 且 key 7我们应该返回 6 作为结果。我们可以使用上面的优化实现来找到键的下限值。只要不变量成立我们就不断地将左指针移到最右边。最终左指针指向小于或等于 key 的元素根据定义下限值。以下是可能的极端情况 — 如果数组中的所有元素都小于 key则左指针移动到最后一个元素。 — 如果数组中的所有元素都大于 key则为错误情况。 — 如果数组中的所有元素都相等且 key则这是我们实现的最坏情况输入。 这是示例
# largest value key # Invariant: A[l] key and A[r] key # Boundary: |r - l| 1 # Input: A[l .... r-1] # Precondition: A[l] key A[r] def Floor(A,l,r,key): while (r-l1): ml(r-l)//2 if A[m]key: lm else: rm return A[l] # Initial call def Floor(A,size,key): # Add error checking if key A[0] if keyA[0]: return -1 # Observe boundaries return Floor(A,0,size,key) Code is written by Rajat Kumar
您可以看到一些测试用例 http://ideone.com/z0Kx4a。 问题陈述给定一个可能有重复元素的排序数组。查找log N时间内输入“key”出现的次数。这里的想法是使用二分搜索查找数组中最左边和最右边出现的键。我们可以修改底函数来跟踪最右边的出现和最左边的出现。 这是示例
# Input: Indices Range [l ... r) # Invariant: A[l] key and A[r] key def GetRightPosition(A,l,r,key): while r-l1: ml(r-l)//2 if A[m]key: lm else: rm return l # Input: Indices Range (l ... r] # Invariant: A[r] key and A[l] key def GetLeftPosition(A,l,r,key): while r-l1: ml(r-l)//2 if A[m]key: rm else: lm return r def countOccurrences(A,size,key): #Observe boundary conditions leftGetLeftPosition(A,-1,size-1,key) rightGetRightPosition(A,0,size,key) # What if the element doesnt exists in the array? # The checks helps to trace that element exists if A[left]key and keyA[right]: return right-left1 return 0 Code is written by Rajat Kumar
示例代码 zn6R6a - Online C0x Compiler Debugging Tool - Ideone.com。 问题陈述 给定一个由不同元素组成的排序数组并且该数组在未知位置旋转。找到数组中的最小元素。我们可以在下图中看到示例输入数组的图示。 我们收敛搜索空间直到l和r 指向单个元素。如果中间位置落在第一个脉冲中则不满足条件 A[m] A[r]我们将搜索空间收敛到 A[m1 … r]。如果中间位置落在第二个脉冲中则满足条件 A[m] A[r]我们将搜索空间收敛到 A[1 … m]。在每次迭代中我们都会检查搜索空间大小如果它是 1我们就完成了。 下面给出的是算法的实现。 你能想出不同的实施方案吗
def BinarySearchIndexOfMinimumRotatedArray(A, l, r): # extreme condition, size zero or size two # Precondition: A[l] A[r] if A[l] A[r]: return l while (l r): # Termination condition (l will eventually falls on r, and r always # point minimum possible value) if l r: return l m l(r-l)//2 # m can fall in first pulse, # second pulse or exactly in the middle if A[m] A[r]: # min cant be in the range # (m i r), we can exclude A[m1 ... r] r m else: # min must be in the range (m i r), # we must search in A[m1 ... r] l m1 return -1 def BinarySearchIndexOfMinimumRotatedArray(A, size): return BinarySearchIndexOfMinimumRotatedArray(A, 0, size-1) Code is written by Rajat Kumar 请参阅示例测试用例 KbwDrk - Online C0x Compiler Debugging Tool - Ideone.com。
练习 1. 称为signum(x, y)的函数 定义为
Signum(x, y) -1 如果 x y 0 如果 x y 1 如果 x y
您是否遇到过比较行为类似于符号函数的指令集它能让二分搜索的第一个实现变得最优吗
2. 实现floor函数的ceil函数复制品。
3. 与你的朋友讨论“二分查找是否是最优的比较次数最少为什么不在排序数组上进行三元搜索或插值搜索与二分搜索相比您什么时候更喜欢三元搜索或插值搜索”
4. 画出二分搜索的树表示相信我这对你理解二分搜索的内部原理有很大帮助。
