让我们从List BinarySearch的重载开始:
public int BinarySearch(T item, IComparer<T> comparer);
众所周知,在使用BinarySearch之前,应该使用适当的IComparer对列表进行排序.但是:要搜索列表,您必须提供T项.当使用一个基于这些项的属性(即使用Linq或delegates /谓词)来搜索列表中的项时,这是相当意外的.因为当我已经拥有我的T项时,我不必搜索它!
现在我在C#中实现C++代码,看到C++程序员在他的代码中到处使用C++样式二进制搜索,如下所示.首先,他制作了一个新的T项目并给了这个T项目他正在寻找的属性.然后他用它搜索列表,找到具有相同属性的列表中项目的索引.当然,C++比较器适用于这些属性.
所以这是在List中查找项目的一种完全不同的方式.BinarySearch创建一个虚拟 T项并搜索一个索引,用它可以检索列表中的实际 T项.从Linq的角度来看,这感觉不自然.
我的问题是:
我是否正确描述了BinarySearch背后的想法？
您是否认为可以使用Linq样式搜索BinarySearch而不首先制作虚拟T项目？
我正在尝试实现一个程序,它将接受用户输入,将该字符串拆分为标记,然后在字典中搜索该字符串中的单词.我解析字符串的目标是让每个标记都是英文单词.
例如:
Input:
aman
Split Method:
a man
a m an
a m a n
am an
am a n
ama n
Desired Output:
a man
我目前有这个代码,它可以完成所有操作直到所需的输出部分:
import java.util.Scanner;
import java.io.*;
public class Words {
public static String[] dic = new String[80368];
public static void split(String head, String in) {
// head + " " + in is a segmentation
String segment = head + " " + in;
// count number of dictionary words
int count = 0;
Scanner …可能重复:
实现二进制搜索有哪些缺陷？
我正在仔细阅读维基百科页面的二进制搜索,并偶然发现了Knuth的一句话:
"尽管二元搜索的基本思想相对简单,但细节可能会非常棘手"
我记得在我的计算机科学课程中实施了几个二进制搜索,但是不记得它非常棘手.然而,这篇文章指出,90%的被调查专业人员在几小时后无法工作.我想假设这不是因为这些是非常糟糕的程序员,而是存在天真实现不能解释的边缘情况.
Knuth所指的细节是什么？如果实现二进制搜索算法,需要注意哪些常见问题？
注意我读了Bloch关于Programming Pearls bug的文章(中点的int溢出).还有别的事吗？
我有一个二进制搜索循环,它在执行路径中被多次命中.
剖析器显示搜索的划分部分(找到给定搜索范围的高和低索引的中间索引)实际上是搜索中最昂贵的部分,大约为4.
(我认为)有效的二进制搜索找到确切的中间值并不重要,只是中间附近的值,在任何一个方向都没有偏差.
是否有一个有点笨拙的算法来mid = (low + high) / 2更快地替换某些东西？
编辑:语言是C#,但是等效的位操作在任何语言中都有效(尽管它可能没有性能优势),这就是我离开C#标签的原因.
最近我听说有一种观点认为二元搜索可以通过将范围分为phi(黄金比例)而不是2来改进.这对我来说是一个很大的惊喜,因为我从来没有听说过这样的优化.这是真的？如果按2和按照phi分算同样有效,那么这是真的吗？
如果没有,是否有任何一般条件,黄金分割搜索比二分查找更快？
UPD:已编辑删除与不相关的维基百科文章的链接.很抱歉误导.
我有一个大约500,000英特的排序数组.目前我通过获取目标int和所有元素之间的差异,然后使用LINQ(非常低效)按最小差异排序来选择正确的索引.
我希望能够做一些与BinarySearch非常相似的事情.
鉴于:
Pos Value
0 10
1 20
2 30
4 50
5 60
如果我想找到值24的最接近的值,我希望返回的索引为1.
鉴于:
int index = myArray.BinarySearch(values, 24);
if (index < 0)
index = ~index;
这返回2,因为它给出了下一个元素,而不是最接近的元素.是否可以编写一个返回最接近索引的IComparer？
给定值:
Value ExpectedReturn
20 1
24 1
25 2
26 2
30 2
我想尽快做到这一点.到目前为止,我在LINQ中所做的一切都与我认为可以通过完善的二进制搜索实现的目标相提并论.谢谢你的反馈.
二进制搜索在最坏的情况下是最佳的 我的导师已经这么说了,但我找不到一本支持它的书.我们从有序数组开始,在最坏的情况下(对于该算法最坏的情况),任何算法总是需要比二进制搜索更多的成对比较.
很多人说这个问题不清楚.抱歉! 所以输入是任何通用排序数组.我正在寻找一个证据,证明任何搜索算法在最坏的情况下至少会进行log2(N)比较(考虑到算法的最坏情况).
我正在尝试使用此二进制搜索代码搜索降序排序数组.然而,在我对它进行排序并尝试搜索之后,它不会带来任何结果,只是一个永远不会消失的加载图标就好像它有一个无限循环.我不确定问题是什么,因为代码看起来合乎逻辑.
这是带有4.0框架的aspx,c#.提前致谢!
protected void Button2_Click(object sender, EventArgs e)
{
String item = TextBox1.Text;
int target = Convert.ToInt16(item);
int mid, first = 0, last = mynumbers.Length - 1;
//for a sorted array with descending values
while (first<=last)
{
mid = (first + last) / 2;
if (target < mynumbers[mid])
first = mid + 1;
if (target > mynumbers[mid])
last = mid - 1;
else
Label11.Text = "Target " + item + " was found at index " + mynumbers[mid];
}
我一直致力于一项似乎是一项让我疯狂的简单任务.所以,如果您喜欢编程挑战......请继续阅读.
我希望能够采用数字范围,例如[1:20],并使用类似于二元搜索算法的机制打印数值.因此,首先打印最低值(在这种情况下为1)然后打印中间值(例如在这种情况下为10)然后将范围分成四分之一并打印值为1/4和3/4(在这种情况下为5)然后分成8个等等,直到打印出范围内的所有值.
应用这个(这里没有必要理解)是一种内存页面访问机制,当首先在中间范围访问页面时,它的行为更有效.
对于这个问题,采用任何数字范围并以上述方式打印值就足够了.
有什么想法吗？假的代码解决方案没问题.我会尝试这一点,但到目前为止我尝试的一切并没有削减它.谢谢.
更新:根据要求,示例[1:20]的所需输出将是这样的:1,10,5,15,3,7,12,17,2,4,6,8,11,13, 16,18,9,19,20
根据所使用的算法,该输出可以以许多类似的方式呈现.但是,我们的想法是首先显示半值,然后是四分之一,然后是八分之一,然后是16分等,而不是先前显示的值.
给定一个排序的数字列表,我需要找到大于给定数字的最小数字.考虑这个清单:
arr=[1,2,3,5,7,11,101,131,151,181,191,313,353,373,383]
假设指定的数字是320.然后,我的方法应该返回353,因为353是大于320的最小数字.
我试图使用略微修改的二进制搜索形式; 但是在执行时,程序进入无限循环.
def modBinarySearch(arr,x):
l=len(arr)
mid=l/2
if arr[mid]>=x and arr[mid-1]<x:
return arr[mid]
elif arr[mid]>x and arr[mid-1]>x:
modBinarySearch(arr[mid:l],x)
else:
modBinarySearch(arr[0:mid],x)
N=int(raw_input())
arr=[1,2,3,5,7,11,101,131,151,181,191,313,353,373,383]
print modBinarySearch(arr,N)
有人可以指出我做错了什么吗？