最新要闻

广告

手机

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

家电

天天看热讯:二分的边界问题

来源:博客园


【资料图】

如何正确判断二分边界?

常见问题

  1. while 内条件是 \(\leq\) 还是 \(<\)
  2. left 和 right 的修改时用不用加 \(1\) 减 \(1\)

例题分析

例:给定一个正整数 \(n( 1 \leq n \leq 1,000)\)。

第二行输入 \(n\) 个整数 \(num_i(0 \leq num_i \leq 10,000)\),保证严格单调递增,第三行输入一个整数 \(k( 0 \leq k \leq 10,000)\)。

若数列中有与 \(k\) 相等的数,输出其下标,否则输出 No

一般来说,我们将二分分为左闭右闭,左闭右开两种类型。

左闭右闭

首先我们根据上面容易出现的两个问题进行分析。

  1. 因为当出现 left == right 是有意义的,所以 while 内使用 left <= right
  2. 如果 num[mid] > k 成立,则下标超过 mid 的数(包括 mid)都不正确,因此 right = mid - 1。若是不成立,也不能判断 num[mid] 是否等于 k,所以不能使 left = mid + 1,而是 left = mid。不过在此题中可以直接判断是否相等,相等直接输出值即可。

左闭右开

还是根据上面两个容易出错的地方分析。

  1. 在左闭右开的区间里,left == right 没有意义,所以 while 内使用 left < right
  2. 如果 num[mid] > k 成立,又由于区间是左闭右开的,所以可以直接使 right = mid。不成立时和上面左闭右闭的相同。

关键词: 常见问题 首先我们 进行分析