-
1 votesanswersviews
3Sum算法问题O（N ^ 2 logn）
使用以下算法： 给定n个整数nums和目标的数组，找到索引三元组i，j，k的数量，其中0 <= i <j <k <n满足条件nums [i] nums [j] nums [k] <目标 . 例如，给定nums = [-2,0,1,3]和target = 2.返回2.因为有两个三元组，其总和小于2： def three_sum_smaller(nums, targe... -
0 votesanswersviews
递增语句以跟踪递归方法中的比较
我正在尝试构造一个递归二进制搜索方法，该方法搜索感兴趣对象的可比较对象的排序数组 . 这是更大算法的一部分，该算法搜索已排序数组的集合并查找集合中所有数组共有的元素 . 目标是使算法的搜索/比较部分尽可能高效 . 线性解决方案应该是可能的 . 这是方法： private static boolean BinarySearch(Comparable[] ToSearch, Comparable To... -
115 votesanswersviews
如何计算二进制搜索复杂度
我听说有人说由于二进制搜索将搜索所需的输入减半，因此它是log（n）算法 . 由于我不是来自数学背景，所以我无法与之相关 . 有人可以更详细地解释一下吗？是否必须对对数系列做些什么？ -
3 votesanswersviews
二维数组中的二进制搜索
我想知道， binary search 可以应用于 2D array 吗？ 数组上的 conditions 会是什么？在2D上排序？ 那时候 complexity 会是什么时候？ 算法如何改变 boundary of the search （minX，maxX，minY，maxY）？ 编辑： 1D上的二进制搜索保持2个指针 minX 和 maxX ..它选择中间索引 (minX+... -
5 votesanswersviews
使用分而治之的方法可以提高时间复杂度，以便在数组中找到最大值和最小值
这是个问题，我在接受采访时被问到了 . 找到最小和最大数组的最佳时间复杂度是多少？ 我回答：O（n） . 遍历数组，跟踪到目前为止发现的最大值和最小值 . 非常简单直接前进 . 面试官问你可以用分而治之的方法来改善它 . 我说可能不是 . 然后谈话继续进行，最后我被要求实施分而治之的方法 . 这里是： public class MinMaxInArray { public static i... -
16 votesanswersviews
数组中的二进制搜索
如何仅使用数组实现二进制搜索？ -
1 votesanswersviews
Java递归二进制搜索
我正在使用递归编写二进制搜索算法，我只是不知道如何开始 . 这是我到目前为止所拥有的： import javax.swing.*; import java.awt.*; import java.awt.event.*; public class BinarySearch implements ActionListener { public static void main(Strin... -
1 votesanswersviews
二进制搜索算法实现
我遇到了多个使用 binary search 的变体来达到最终答案的问题 . 这些问题包括找到数字的平方根，检查数字是否是完美的正方形，在旋转数组中找到最小值，在数组中查找数字的第一个索引等 . 所有算法都包含适当修改的低，高和中变量 . 我在网上阅读了这些算法的几种变体，这些算法总是有很多错误，导致它错过了极端情况 . 对于以下变化，是否有任何标准可以帮助我理解何时应该使用哪一个？ 1. Ini... -
0 votesanswersviews
在内存限制的未排序输入中查找缺少的数字
我正在阅读有关在 Programming Pearls 中从一系列40亿32位整数中找到缺失数字的问题，但无法得到解决方案 . 给定一个顺序文件，其中包含最多4亿个随机顺序的32位整数，找到一个不在文件上的32位整数 . 约束：主内存的几个字节数，但在磁盘上充分使用extrernal暂存文件 所描述的解决方案是一个过程，我们使用高位分隔范围中的数字（在第一遍中我们将那些带有前导 0 位的数字写... -
0 votesanswersviews
使用随机元素进行二进制搜索
我知道二进制搜索具有 O(logn) 的时间复杂度来搜索排序数组中的元素 . 但是，让我们说如果不选择中间元素，我们选择一个随机元素，它将如何影响时间复杂度 . 它仍然是 O(logn) 还是其他的东西？ 例如：一个大小为18的数组中的传统二进制搜索将会像18 - > 9 - > 4那样下降... 我修改的二进制搜索ping一个随机元素，并决定根据值删除右边部分或左边部分 . -
3 votesanswersviews
如何使用二进制搜索在数组中找到插入点？
数组中二进制搜索的基本思想很简单，但如果搜索无法找到确切的项目，它可能会返回“近似”索引 . （我们有时可能会返回一个值大于或小于搜索值的索引） . 为了寻找确切的插入点，似乎在得到大致的位置之后，我们可能需要向左或向右移动确切的插入位置，所以在Ruby中，我们可以做 arr.insert(exact_index, value) 我有以下解决方案，但 begin_index >= end_... -
8 votesanswersviews
使用二进制搜索优化大型if-else分支
所以在我的程序中有一个if-else分支，大约有30个if-else语句 . 这部分每秒运行超过100次，因此我将其视为优化的机会，并使用函数指针数组（实际上是 balancer 树映射）进行二进制搜索，而不是进行线性if-else条件检查 . 但它的速度比以前的速度快了约70％ . 我做了一个简单的基准测试程序来测试这个问题，它也给出了类似的结果，if-else部分运行得更快，无论是否有编译器优... -
0 votesanswersviews
修改二进制搜索中的无限循环
我正在尝试实现二进制搜索的修改版本，它从已排序的数组返回给定键的下一个最大值的位置 . 这是代码 - （lli指long long int） lli search(vector<lli>arr,lli key) { lli low=0,high=arr.size() - 1,mid,pos=-1; while(low<=high) { m... -
4 votesanswersviews
按功能javascript / lodash二进制搜索
对于大多数此类操作，我们使用的是lodash库 . 我对其他建议持开放态度，但可能只是在导入新的lib之前自己编写函数 . lodash有 sortedIndexOf ，它在排序数组中执行二进制搜索（返回匹配索引，如果未找到则返回-1） . 它还有 sortedIndexBy ，它使用二进制搜索，找到插入新元素的索引，您可以在其中指定用于进行排序比较的函数（如果未找到则返回有效索引） 我找不到一个... -
3 votesanswersviews
两个排序数组中的最小和 - 二进制搜索解决方案
我正在努力解决面试实践问题 . 问题是： 给定两个按升序排序的整数数组和一个整数k . 定义sum = a b，其中a是第一个数组中的元素，b是第二个数组中的元素 . 找出所有可能总和中的第k个最小和 . 例如给定[1,7,11]和[2,4,6] . 对于k = 3，返回7.对于k = 4，返回9.对于k = 8，返回15 . 我们将n定义为A的大小，将m定义为B.我知道如何使用堆（O（k l... -
1 votesanswersviews
Java - binarySearch（） . 如何为拼写检查设置binarySearch
我正在做一个拼写检查项目 . 我有一个单词列表，然后是Gettysburg地址，其中一些单词拼写错误 . 我的工作是确定哪些单词拼写错误，然后在我打印出地址时打印出拼写错误字样的星号或其他内容 . 我的问题是在binarySearch部分 . 我不确定语法，javadoc看起来像中文 . 这是我的源代码（binarySearch是底部） /* * Assignment 1: Spell Chec... -
0 votesanswersviews
二进制搜索没有图书馆方法
我正在尝试构建一个遍历排序数组的binarySearch方法，并评估给定的元素（以 int target 给出）是否存在 . 它将通过评估平均值是大于还是小于目标值来做到这一点，并相应地循环遍历数组的第一个或第二个 . 我想我有基本的代码，但我遇到了一些问题： int target = 0; （返回true）=>正确 int target =（3,6,9）; （返回false）=&g... -
1 votesanswersviews
Java前缀使用二进制搜索进行搜索
我一直在尝试使用java的二进制搜索方法在一个单词数组（一个词典）中搜索一个特定的字符串，然后确定该字符串是单词，前缀还是单词 . 如果返回的索引大于或等于零，则该字符串为单词 . 如果返回的索引小于零，那么我必须确定它不是单词还是前缀 . 例如，例如，当查找“ela”时，返回的值可能是-137 . 这意味着“ela”不在词典中，但是如果它被插入则它将在索引136处 . 这也意味着如果索引136处... -
2 votesanswersviews
如何让二进制搜索方法返回false？
我正在使用C＃中的二进制搜索方法作为练习，如果数字在列表中，则返回true，但如果数字不在列表中，则无法返回false . 如果最后条件是UB = LB，但是SearchKey不等于MP，我曾考虑过做其他事情 . 有什么建议？ static bool search(List<int> numbers, int searchKey) { int UB = numb... -
2 votesanswersviews
使用二进制搜索以正确的索引打开数组中的空格
我应该创建两个方法：第一个方法，bSearch，是一个二进制搜索算法 . 第二个方法insertInOrder应该从bSearch方法中获取索引，并在数组中找到该索引，通过将该数组的所有其他元素移位，在该索引处打开一个点，然后插入key / int那个指数 . 将从包含25个整数的文本文件中接收整数 . 我不是要做任何副本或额外的数组来执行此操作，我应该编码然后解码insertInOrder方法中... -
-1 votesanswersviews
如何使用递归进行分而治之以找到A [i] = i
我正在尝试使用递归二进制搜索方法，以便找到A [i] = i时给出一个按升序排序的不同数量的'n'元素 . 我理解如何使用递归二进制搜索方法给定我需要搜索的目标，但是当我必须将键值增加1并搜索A [i] = i时，我似乎无法实现 . public static int match_dac( int[] A, int n ) { return dnq(A, 0, n-1, 0); } p... -
3 votesanswersviews
使用布尔值在数组中进行二进制搜索
我有一个布尔值的数组 . 但是像这样的元素序列：首先是 true 值，然后是 false 值 . 例如， boolean[] booleans = {true, true, true, true, true, false, false, false, false, false, false}; 所以现在我们有一个带有布尔值的排序数组，如果存在 true 值，则从 ... -
48 votesanswersviews
实现二进制搜索有哪些陷阱？
二进制搜索比它看起来更难实现 . “尽管二元搜索的基本思想相对简单，但细节却令人惊讶地难以理解......” - 唐纳德克努特 . 哪些错误最有可能被引入新的二进制搜索实现？ -
1 votesanswersviews
如何在执行二进制搜索时正确显示数组中不存在值
我正在尝试在JavaScript中实现二进制搜索 . 我能够返回目标元素的索引，但是，我的程序没有返回“-1”表示目标值不在数组中 . 例如，如果我有[12,39,52,61,88,100]的数组，并且我在我的二进制搜索函数中输入目标值“200”，则它不返回“-1”以指示即使我构造了我的else语句来执行此操作，该值也不存在于数组中 . 谁能告诉我我做错了什么？提前致谢 . 我的代码： funct... -
0 votesanswersviews
在排序的数组中找到与n最接近的值，而不是经过
对于这个问题，我有一个排序的双精度数组 . 我需要能够快速有效地找到最接近但不超过n的值的索引 . 效率是关键，赋值状态可以在O（log n）中完成，因此我假设它可以通过某种修改的二进制搜索来完成 . 我知道之前已经问过这个问题，但是我发现所有的答案都是假设一个未排序的数组，或者只是通过整个数组循环比较差异 . 任何指导表示赞赏 . 谢谢 . -
1 votesanswersviews
Java - 比较线性搜索和二进制搜索的性能[重复]
可能重复：线性搜索和二进制搜索有什么区别？ 编写一个程序，在0到100的范围内生成20个随机整数 . 按降序对数组进行排序 . 然后，接受来自用户的整数输入 . 然后，使用此编号搜索阵列 . 比较线性搜索和二分查找的性能 . 这是我的代码 import java.util.Arrays; import java.util.Scanner; public class search ... -
3 votesanswersviews
找到二进制搜索结果的最重复
假设我有一个有大量重复的有序数组： var array = [ 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, ]; 我还有代码对排序数组中最接近的值的索引执行二进制搜索： funct... -
2 votesanswersviews
二进制搜索卡住无限循环？
我创建了这个二进制搜索，但它似乎每次都陷入循环 . 所有它的检查是一个向量 . 我不知道我需要改变什么我已经尝试了很多不同的东西 . [1,2,4,6]如果我搜索4是永远不会被发现它继续击中较低=中间1 . bool SortSearch::binarySearcher(int size, int val) { int lower = 0, upper = size - 1, mid; ... -
7 votesanswersviews
这种二进制搜索有名称吗？
在今天编写一些代码时，我发生了一种情况，这种情况导致我编写了一种我以前从未见过的二进制搜索 . 这个二进制搜索是否有名称，它真的是一个“二进制”搜索吗？ 动机 首先，为了使搜索更容易理解，我将解释产生其创建的用例 . 假设您有一个有序号码列表 . 系统会要求您在列表中找到最接近x的数字索引 . int findIndexClosestTo(int x); 对 findIndexClosestTo... -
0 votesanswersviews
为什么在SAP ABAP中重复输入条目时，为什么读取带二进制搜索的表会返回第一个条目？
二进制搜索适用于已排序的条目 . 根据算法，如果条目数（n）是偶数，则它首先搜索第n / 2条目 . 如果是密钥，则返回，否则检查密钥是否小于或大于位置的n / 2 . 如果它更小，那么搜索从索引1继续到n / 2 -1，丢弃剩下的一半 . 类似地，该过程重复直到找到搜索到的密钥 . 在奇数个条目的情况下，中间位置是n-1/2 . 所以我的问题是，如果有重复的条目，我们按升序排序，如1112223...