Tag: 二进制搜索

二进制搜索和哈希表搜索

我想找出一个字典查找和一个数组的二进制搜索查找之间的权衡点。 我期待着字典的恒定时间查找，以及二进制搜索的对数时间查找，具体取决于集合的大小，二进制搜索对于较小的集合表现更好。 但是，当我看到以下结果时，我感到很惊讶： 我很惊讶：1。二进制搜索首先以对数方式增长，然后增长得更快。 哈希起初非常一致，但随后开始慢慢增长。 3.二进制搜索永远不会比哈希查找更好。 以下是我的代码。 我做错了什么？ class Program { static void Main(string[] args) { var r = new Random(); var targets = Enumerable.Range(0, 1000 * 1000).Select(_ => r.Next(int.MaxValue)).ToList(); for (int totalCount = 1; totalCount r.Next(int.MaxValue)).Distinct().Select(v => new thing(v)).OrderBy(t => t.value).ToArray(); var d = a.ToDictionary(t => t.value); var watch = new System.Diagnostics.Stopwatch(); { watch.Start(); […]

获取字典中最大的密钥

我有一个包含整数键的字典。 我想得到最大的钥匙。 我不跟踪密钥，因此它们可能是连续的（例如1,2,3,4,5,6），但可能会跳过（1,3,4,5），尽管我怀疑这有什么不同。 我只是使用二进制搜索还是有方法？ 据我所知，你几乎无法击败二元搜索这么简单的任务 – 也许你可以把它减半。

扩展二进制搜索算法以查找要在数组中搜索的键值的第一个和最后一个索引

问题是扩展二进制搜索算法以最有效的方式查找排序数组中所有出现的目标值。 具体地说，算法的输入是（1）整数的排序数组，其中一些数字可能出现不止一次，以及（2）要搜索的目标整数。 算法的输出应该是一对索引值，指示数组中第一次和最后一次出现的整数（如果确实发生的话）。 源代码可以是c＃，c，c ++。 另外，我们可能需要查找索引的最大和最小比较数是多少？

二进制搜索已排序的数组

我正在尝试使用此二进制搜索代码搜索降序排序数组。 然而，在我对它进行排序并尝试搜索之后，它不会带来任何结果，只是一个永远不会消失的加载图标，就像它有一个无限循环一样。 我不确定问题是什么，因为代码看起来合乎逻辑。 这是带有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]) last = mid – 1; […]