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，建议构造对应测试样例，断点调试代码，这比任何回答都来的直接、深刻

[AimeSuzy]

target不存在的情况就是 target大于数组最大值或者小于数组最小值。当target大于数组最大值时，其插入点就是Numsize， 必有Nums[Numsize-1] != target；当target小于数组最小值时，其插入点就是0，所以j = i -1 = -1

[gopherHsu]

楼上回复的

target不存在的情况就是 target大于数组最大值或者小于数组最小值。
这个说法不对
target不存在时也有可能是这样的情况：数组 = [1,2,3,6,7,8]， target=4, 这个时候target也不存在
在查找左边界的时候，如果：

1. target大于数组最后一个元素，i = nums.length
2. 其他target不在数组中的情况 $i \in [0, nums.length - 1]$

上面两种情况对应判断代码的两种情况：

// 未找到 target ，返回 -1
if (i == nums.length || nums[i] != target) {
    return -1;
}

[csj-9-9]

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

[krahets]

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

[lynnlee0522]

https://leetcode.cn/problems/find-smallest-letter-greater-than-target/description/
这道题目非常适合这一章节的内容

[twx0504]

哈喽大家，关于target+1的我看了好久，一下是我的理解：

：当传入target的时候，binarySearchInsertion 始终都会返回最左target的索引。当传入target + 1的时候则会返回最左target + 1的索引。当最左target + 1的索引 - 1便会得到最右target的索引。

function binarySearchRightEdge(arr, target) {
  // find the insertion point of target + 1
  const i = binarySearchInsertion(arr, target + 1); // i is the index just past the last occurrence of target.
  const j = i - 1; // i - 1 will be the rightmost target.
  if (j === -1 || arr[j] !== target) return -1;
  return j;
}

我不确定我的理解到不到位，如果有误，希望大家可以多多给予指导哦

[twx0504]

请问关于转化为查找元素的实现是这样吗？😂

function binarySearchEdge(arr, target) {
  let i = binarySearchInsertion(arr, target - 0.5); // 最左边界
  let j = binarySearchInsertion(arr, target + 0.5) - 1; // 最右边界
  if (i === arr.length || arr[i] !== target) i = -1;
  if (j === -1 || arr[j] !== target) j = -1;
  return { i, j }; // 返回对象 i & j
}

[zhengComing]

如何理解 target + 1的操作?
由于寻找target的插入位置其实就是寻找其左边界，即寻找第一个 >= target的元素，而右边界其实是寻找第一个<= target的元素，此时即可利用寻找左边界的做法将其转换为 >= target+1 ,由于数组元素均为整数，所以j指向即为<=target元素的第一个索引

[lory1610]

target + 1这个操作，其实打断点调试就容易明白了。
依据文中样例，target=6， target+1=7，用二分查找插入点，找到的是7最左边的索引。
因为二分查找的有序性，对返回的索引减一就是target=6最右边的一个位置。
有讲得不对的地方，请大家多指教。

[triumphant-i]

因为target+1也可能有一堆相同的值。所以相当于111122222333这种排列。利用查找相同元素中的最左端函数，即一定有前一个元素的最右端与之相邻！而适用x+/-0.5，同理，这个不存在的元素的最左端一定与x的最右端相邻！（太酷啦orz

[6mmLIU]

target+1，需要明白一点，target不是索引，是你要找的目标值，target+1实际上指的就是数组中比target大的下一个元素。计算这个元素的最左边界，减去1就是target的最右边界了。我的个人理解，如有错误，请多多指正