我居然百度不出来一个正确的（不使用库的）对有序数组进行二分查找插入的算法代码！

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1629 天前的主题，其中的信息可能已经有所发展或是发生改变。

各位怎么看？

数组

算法

插入

查找

15 条回复 • 2020-06-12 09:37:00 +08:00

hsiang271828

2020-06-08 12:19:25 +08:00 via iPhone

自己写一个啊，造福后人

BiteTheDust

2020-06-08 12:21:48 +08:00

对数组插入的复杂度是 O(n)的二分在这里就失去意义了

Vegetable

2020-06-08 12:22:27 +08:00

是不是因为太简单了，没什么操作空间？

Vegetable

2020-06-08 12:24:44 +08:00

这个问题应该是另一个问题：如何使用对有序链表使用二分法进行查找。

Vegetable

2020-06-08 12:25:12 +08:00

*如何对使用二分法查找有序链表

Vegetable

2020-06-08 12:25:33 +08:00

？？？
*如何使用二分法查找有序链表

Hstar

2020-06-08 12:26:19 +08:00

你这题目意义不明，是吐槽百度搜索结果烂？

oahebky

2020-06-08 12:31:08 +08:00 via Android

@BiteTheDust
从算法角度确实影响很小。
后来看一个网友的评论学到了不用查找直接插入的一次遍历算法。

oahebky

2020-06-08 12:39:45 +08:00 via Android

@Hstar
一个是结果不咋地，
重点是，另外一方面是好多博客的算法实现考虑不全，是错的。

基本上用 c 和 Java 实现的，看到百分九十的实现都是两个边界没有考虑进去，是错的。

netnr

2020-06-08 13:02:48 +08:00

https://www.netnr.com/run/code/4612213862936131906

来源于互联网

oahebky

2020-06-08 13:46:28 +08:00

@netnr #10 原文：“https://www.netnr.com/run/code/4612213862936131906 来源于互联网”
======
回复：
你贴的这个就是我看到的错误之一。
我说的是二分查找后插入；网上的部分实现在数组中没有相等于目标元素的情况下就无法正确插入。

RJH

2020-06-08 13:56:30 +08:00

对有序数组进行二分查找插入是什么意思啊？二分查找我倒是知道，二分查找插入就真的不懂了

mangoDB

2020-06-08 14:04:29 +08:00

怎么看？换 Google 、必应试试？

netnr

2020-06-08 14:07:09 +08:00

并不是错误的

jmc891205

2020-06-12 09:37:00 +08:00

https://en.cppreference.com/w/cpp/algorithm/lower_bound