问题标签 [linear-search]

线性搜索和二分搜索有什么区别？

我正在寻找优化这个线性搜索：

数组已排序，函数应该返回大于或等于键的第一个元素的索引。它们的数组不大（少于 200 个元素），并且会为大量搜索准备一次。如果需要，可以将第 n 个之后的数组元素初始化为适当的值，如果这样可以加快搜索速度。

不，不允许二分查找，只能线性查找。

编辑：我关于这个主题的所有知识现在都在这篇博文中进行了总结。

有人可以解释为什么在未排序的数组数据结构中查找项目的平均步骤数是 N/2？

我试图得出确定性线性搜索算法的平均案例运行时间。该算法按照 A[1]、A[2]、A[3]...A[n] 的顺序搜索未排序数组 A 中的元素 x。它在找到元素 x 时停止或继续直到到达数组的末尾。我在维基百科上搜索，给出的答案是 (n+1)/(k+1) 其中 k 是 x 出现在数组中的次数。我以另一种方式接近，得到了不同的答案。谁能给我正确的证据，并让我知道我的方法有什么问题？

我没有得到 (n+1)/(k+1) 的简化。

如何从 C 中的线性搜索中打印多个搜索？

是否可以返回一个以上的值，例如，如果数组有多个等于目标的元素？

I've tried using both binary search, and while loops and for loops in my searches and the same problem is occurring.

When my original program comes to this function call, the linear search function (displayContent) will always assign -1 to position, and after the function call the program breaks and exits.

I have tried to rearrange my program. Like I said, I tried for loops and while loops with both binary and linear search.

I am also using a structure data type of

Here is my function call

Here is my function definition

我试图比较哈希表查找和线性搜索的性能。我创建了一个包含 1000 个项目的哈希表，发现在哈希表中查找所需的时间为 0.0002（我曾经DateTime.Now在查找前后找出系统时间并减去它们）。我在一个数组中有相同的 1000 行，并使用线性搜索查找相同的值。结果证明它比哈希表查找所花费的时间要少。

我认为哈希表比线性搜索更快。它是如何工作的？

我的程序没有编译错误，但输出不正确。示例输入：

数组大小：5
输入数字：5 4 3 2 1
//排序：1 2 3 4 5
搜索：1
输出：在索引 4 找到数字 1

输出应该是在索引 0 处找到的数字 1，因为这些数字已经排序。我将如何将其更改为这个。

我正在尝试编写一个程序，该程序在一个名为的数组中进行顺序搜索和二进制搜索，该数组items具有 10000 个排序的随机int值。调用的第二个数组targets加载了 1000 个int值（来自items数组的 500 个值和不在数组中的 500 个值items）。

基本上，搜索需要通过 items 数组来查找数组中的int值targets。这是我的代码：

编辑：输出应该是这个>

395

986

-1

14

-1

顺序搜索时间：40 毫秒

395

986

-1

14

-1

二分查找时间：0毫秒

我有一个关于我正在处理的问题的问题。我必须随机播放视频而不重复视频。每个播放列表中的每个视频只能播放一次。每个视频都有一个从 0 到 max_video_count 的唯一 ID，该 ID 在运行时确定（取决于服务器）。

我现在要做的是，我创建了一个链接列表，其中添加了每个播放视频的唯一 ID。比我随机创建一个介于 0 和 max_video_count 之间的随机数，如果该数字已经在链表中，则进行线性搜索，如果是，我计算一个新数字..然后再次线性搜索..等等！

显然这不是很实用，有时需要很长时间才能找到一个元素。特别是当已经播放了很多视频时。

所以我想，我实现了二进制搜索而不是线性搜索，但这给我带来了我必须先对列表进行排序的问题。因此，我的下一步是思考，我在插入新的 unique_id 时对列表进行排序，而不是进行二分搜索。

我知道与 O(n) 线性搜索相比，二分搜索是 O(log n)，这是一个很大的进步。但是对列表进行排序也是 O(n)，因为要找到正确的位置，我必须再次进行线性搜索.....所以我找到了解决方案，而不是二进制搜索将 O(log N * n) 与O(n) 线性搜索 -> 快速线性搜索。是对的吗？也许我的整个方法都是错误的......但我还想不出更好的东西......

我对算法很陌生，所以如果有人能在这里启发我会很好:-)

问候马库斯