chapter_searching/binary_search_edge/

[giscus[bot]]

chapter_searching/binary_search_edge/

一本动画图解、能运行、可提问的数据结构与算法入门书

https://www.hello-algo.com/chapter_searching/binary_search_edge/

[limuzi9806]

啊，我太菜了，看了好几遍才看出来为什么要查找元素只出现一次也能找出来。。。。。
感谢k神和各位贡献者！

[zrcoder]

如果数组元素是 []int 类型，那么查找右边界可以转化成查找左边界：要在数组中找到 target 的右边界，可以找 target+1 的左边界再来确定结果。

其他类型的话也可以用相同的思路，稍微麻烦点，比如 []string， 如果确定每个元素只含小写字母，要找 ‘abc’的右边界，可以先找 ‘abca' 的左边界。

[zrcoder]

补充一下 go 的标准库关于二分查找的核心方法 sort.Search，就是用来查找左边界的，没有提供查找右边界的方法，仔细考虑 go 语言大道至简的理念，或许确实大多数场景的找右边界可以转成找左边界。

[zhuasdfg]

i,j的取值范围边界看了我好久，太妙了

[fiona-liu12]

将查找最右一个 target 转化为查找最左一个 target + 1 这个妙啊

[buynonsense]

还是没有看懂，最左一个是target的话，为什么target+1是最右一个

[buynonsense]

我现在看懂了！

[buynonsense]

我之前犯迷糊了，我没有意识到：查找左边界 查找右边界 是用2个函数完成的。
此外我有一个疑问：在2.转化为查找元素，target-0.5是直接找到了最左的target还是找到了最左的target的左边一个元素(在图10-8的话就是3这个元素)，再通过索引+1找到最左target？

[amoyonglee]

图 10-8 , 查找元素 target - 0.5 , 在结束循环时, 指针 j 此时指向元素 3 , 指针 i 此时指向最左边的 target 元素 6 , 所以直接返回指针 i 就是返回最左 target , 不用再运算了. ( 经常跟着评论里的迷糊一起迷糊, 不过想明白后印象也会更加牢固 )

[MancityOasis]

在查找右边界判断时，nums[j] != target这句代码是不是可以省略呀~

[krahets]

Hi，不可以省略，因为数组中可能不存在 target 这个元素

[MancityOasis]

哦是我理解错了！谢谢k神

[hero-lc]

没有看懂，最左一个是target的话，为什么target+1是最右一个

[llhznb]

这是个整数数组，target+1就是那个紧挨着比target大的数，原方法i是第一个target，现在i是第一个target+1。那i左边即target的右边界。j在这个位置

[Cupcc]

仔细看，target+1其实不是最右一个，是第一个大于target的元素索引，返回的时候将索引-1，即为target最右元素。
为什么可行？target+1在数组中的时候很好理解。直接就是target+1的索引位置，然后-1就是target的最右位置。
因为当你搜索不到target+1的时候如何理解？ 比如[0,1,4,4,4,7]，查找target+1=5 返回index = 5;只要比target大一丢丢的数，索引位置就会落在target的右侧一个位置，即nums[5]=7的位置。 这个大一丢丢的数在「整数」序列中取1即可。

[WheatJack]

按照最左查找方法 如果在它的基础上+1 那么找到的值的左边的一个值 应该是最接近最右边的
* 例如 1 2 3 4 5 6 6 6 6 6 6 6 7
* target是6 想找到最右 那么target +1 7 那么找到第七个值的索引 -1 那么就是最右边的6了

[yangzkalone]

简单来说，target+1元素的左边界，就是target元素的右边界，因为两者是左右相邻挨着的。作者的图例不是很好，不够形象

[werchaotica]

将查找最右一个target转化为查找最左一个target+1这个方法，是不是只有int类型可以这样做？像float类型的就只能用修改nums[m]==target时的边界操作来实现。不知道我理解的有没有问题

[krahets]

是的，这个方法不适用于 float 类型

[EndlessCheng]

浮点数也是可以的，比如 Go 中有 math.Nextafter，可以算出（往正/负方向的）下一个浮点数，比如 math.Nextafter(1, 2) 是 1.0000000000000002

[krahets]

确实，只要能确定该精度下的下一个元素就行。值得注意的是，有些语言并未提供 built-in 的寻找最近浮点数的函数，例如 Python<3.9 （可以用 numpy 的 np.nextafter()）和 JavaScript 。

[EndlessCheng]

相关题目：34. 在排序数组中查找元素的第一个和最后一个位置

[hpstory]

哇，大师球

[wbzyo]

这个target+1也太妙了，还有一些疑问，希望k神或其他小伙伴帮忙解答一下

1. 10.3.1里查找左边界不包含target出现的越界情况，是因为target比数组里所有数都大，然后i一直向右走，最后跑到j+1的位置结束循环，导致越界吗？
2. 10.3.2里的复用查找左边界，target不存在，怎么就会使得j=i-1这步后，j的值为-1了呢？

[krahets]

Hi，建议构造对应测试样例，断点调试代码，这比任何回答都来的直接、深刻

[csj-9-9]

“请返回数组中最左一个元素 target 的索引”？感觉自己的阅读理解好差啊！感觉这句话表达的意思是“返回数组第一个元素的索引”。改成“请返回 target 元素在数组中的最左索引”是不是会好点啊

[krahets]

Hi ，这句话需要把“元素 target”看为一个整体（书中以及其他技术文档中有许多这样的表述，可能需要习惯一下）