我有一个较大的字符串数组,我想用作查找.

我正在使用in_array(),但我怀疑它做了一个简单的循环 - 有没有人知道in_array()算法是否使用了bsearch算法？

我正在尝试使用objective-c块实现二进制搜索.我正在使用该功能indexOfObject:inSortedRange:options:usingComparator:.这是一个例子.

// A pile of data.
NSUInteger amount = 900000;
// A number to search for.
NSNumber* number = [NSNumber numberWithInt:724242];

// Create some array.
NSMutableArray* array = [NSMutableArray arrayWithCapacity:amount];
for (NSUInteger i = 0; i < amount; ++i) {;
    [array addObject:[NSNumber numberWithUnsignedInteger:i]];
}
NSTimeInterval start = [NSDate timeIntervalSinceReferenceDate];

// Run binary search.
int index1 = [array indexOfObject:number 
                    inSortedRange:NSMakeRange(0, [array count]) 
                          options:NSBinarySearchingFirstEqual 
                  usingComparator:^(id lhs, id rhs) {
                      if ([lhs intValue] < [rhs intValue]) {
                          return (NSComparisonResult)NSOrderedAscending;
                      } else …

一次比较每次迭代二进制搜索有什么意义？你能解释它是如何工作的吗？

容易出问题和已知算法:

我有一个拥有100名成员的大阵容.前X个成员为0,其余为1.查找X.

我通过二分搜索来解决它:检查成员50,如果它是0 - 检查成员75等,直到我找到相邻的0和1.

我正在寻找一个针对二维相同问题的优化算法:

我有二维数组100*100.在0-X行和0-Y列上的那些成员是0,其余的是1.如何找到Y和X？

在今天编写一些代码时,我发生了一种情况,这种情况导致我编写了一种我以前从未见过的二进制搜索.这个二进制搜索是否有名称,它真的是一个"二进制"搜索吗？

动机

首先,为了使搜索更容易理解,我将解释产生其创建的用例.

假设您有一个有序号码列表.系统会要求您在列表中找到最接近x的数字索引.

int findIndexClosestTo(int x);

findIndexClosestTo() 始终遵循此规则的呼叫:

如果最后的结果findIndexClosestTo()是i,那么指数越接近i当前调用的结果的概率越大findIndexClosestTo().

换句话说,我们需要找到的索引更接近于我们找到的最后一个索引而不是它.

举个例子,想象一个在屏幕上左右走动的模拟男孩.如果我们经常查询男孩所在地的指数,那么很可能他就在我们找到他的最后一个地方附近.

算法

鉴于上面的情况,我们知道最后的结果findIndexClosestTo()是i(如果这实际上是第一次调用该函数,i默认为列表的中间索引,为简单起见,尽管单独的二进制搜索找到第一个结果调用实际上会更快),并且该函数已被再次调用.给定新数字x,我们按照此算法查找其索引:

1. interval = 1;
2. 我们正在寻找的号码x,定位于i？如果是这样,返回i;
3. 如果不是,请确定x是高于还是低于i.(请记住,列表已排序.)
4. 将interval指数移向方向x.
5. 如果我们x在新位置找到,请返回该位置.
6. 双倍interval.(即interval *= 2)
7. 如果我们已经通过x,请返回interval索引,设置interval = 1,转到4.

鉴于上述概率规则(在Motivation标题下),我认为这是找到正确索引的最有效方法.你知道更快的方法吗？

我有一个大文本文件(5Mb),我在我的Android应用程序中使用.我将文件创建为预先排序的字符串列表,文件创建后不会更改.如何对该文件的内容执行二进制搜索,而无需逐行读取以查找匹配的字符串？

有没有人知道在序列号列表中找到重复的比线性更快的算法？我现在在Java工作,但任何语言或伪代码都没问题.

例如,给定此int []输入:

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 7 | 8 | 9

输出可以是指数或值'7'.

我知道O(n)线性时间的明显遍历,但我正试图通过二进制搜索来确定这是否可行O(log n).

鉴于以下语句,取自此 Oracle Java教程,与类Collections的binarySearch()方法有关:

两个表单的返回值相同.如果List包含搜索键,则返回其索引.如果不是,则返回值为 ( - (插入点) - 1),其中插入点是将值插入List的点,或者第一个元素的索引大于值或list.size ()如果List中的所有元素都小于指定值.

为什么返回值binarySearch()不仅仅返回负指数而不是负指数减1？(上面引用的粗体部分).

简而言之:为什么(-(insertion point) - 1)而不仅仅是(-(insertion point))？

提前致谢.

我正在阅读Robert Sedgewick的算法第4版,他有以下任务:

假设你有一个N层建筑和2个鸡蛋.假设如果鸡蛋被扔掉F楼或更高楼层,鸡蛋就会被打破,否则就会破裂.您的成本模型是投掷次数.设计一个策略来确定F,使某些常数c的投掷数量为~c√F.

任务的第一部分是在2√N步骤中找到F,这是一个解决方案:

第1部分的解决方案:

• 要达到2*sqrt(N),请在楼层sqrt(N),2*sqrt(N),3*sqrt(N),...,sqrt(N)*sqrt(N)下降鸡蛋.(为简单起见,我们假设sqrt(N)是一个整数.)
• 假设蛋在k*sqrt(N)水平处破裂.
• 然后使用第二个蛋,您应该在区间(k-1)*sqrt(N)到k*sqrt(N)中执行线性搜索.
• 总共可以在最多2*sqrt(N)的试验中找到F楼.

他还提供了~c√F部分的提示(第2部分):

第2部分的提示:1 + 2 + 3 + ... k~1/2 k ^ 2.

那么~c√F步骤的算法是什么？

我有一个实际值的排序(升序)数组,称之为(可能重复).我希望在给定一系列值[x,y]的情况下,找到索引j存在的所有值(i)的索引,使得:j> i和x <= a [j] -a [i] <=或者简单地说,找到在给定范围内存在"前向差异"的值.

输出是一个长度为a.Length的布尔数组.由于数组是对所有前向差异进行排序,因此x和y为正.

我设法做的最好的是从每个索引开始查看它前面的子阵列并执行二进制搜索x + a [i]并检查是否[j] <= y + a [i].我认为这是O(n log n).有更好的方法吗？或者我可以做些什么来加快速度.

我应该注意到,最终我想在同一个数组a上搜索许多这样的范围[x,y],但是范围的数量远小于数组的长度(小4-6个数量级) - 因此我更关心搜索的复杂性.

例:

a= 0, 1, 46, 100, 185, 216, 285

范围x,y = [99,101]应该返回:

[true, true, false, false, true, false, false]

仅对于值0,1和185在该范围内具有前向差异.

内存中的代码可能有一些错误:

int bin_search_closesmaller(int arr[], int key, int low, int high)
{
    if (low > high) return high;
    int mid = (high - low)/2;
    if (arr[mid] > key) return bin_search_closesmaller(arr, key, low, mid - 1);
    if (arr[mid] < …