标签: binary-search

我有两个系列,每个系列包含大约40,000个项目.

列表2中的元素通过外键链接到列表1的元素.

对于列表一的每个元素,我想在列表二中找到相应的元素.

像这样的东西:

foreach(var item in list1)
{
  var match = list2.Where(child => child.ID == item.ChildID).FirstOrDefault();
  item.Child = match;
}

这有效,但它很慢.

现在,list1和list2都是按照这些键从数据库中排序的.因此list1按ChildID排序,list2按ID排序(相同值).

我认为二进制搜索会大大提高速度,但我在某处读到了Linq会在Where子句中为列表选择最合适的策略.也许我需要明确地转换为排序列表？或者我可能需要使用比较器实现自定义二进制搜索算法？

任何见解都表示赞赏.

谢谢.

例如,假设我想在文件中找到特定的单词或数字.内容按排序顺序(显然).由于我想在文件上运行二进制搜索,将整个文件复制到一个数组然后运行二进制搜索似乎真的浪费时间...我已经有效地将它变成了线性时间算法,因为我'在我运行搜索之前,我必须花费O(n)时间复制该darn文件.

有更快的方法吗？是否有类似lseek的东西可以使用行而不是字节？

如果没有,我最好只做一次线性搜索(假设我只在整个程序期间运行一次搜索)？

问题是扩展二进制搜索算法以最有效的方式查找排序数组中所有出现的目标值.具体地说,算法的输入是(1)整数的排序数组,其中一些数字可能出现不止一次,以及(2)要搜索的目标整数.算法的输出应该是一对索引值,指示数组中第一次和最后一次出现的整数(如果确实发生的话).源代码可以是c#,c,c ++.

此外,我们可能需要查找索引的最大和最小比较数是多少？

在我的Android应用中,我想要一个带自动完成功能的输入字段.项目数量约为300000.最佳解决方案似乎是将项目放入文件(在SD卡上),每行一个项目,每行将具有相同的字符数,以便我可以寻找特定的行号.如果用户在文本字段中输入内容,我将二进制搜索(通过RandomAccessFile)文件并显示建议.

我希望自动完成能够超快(理想情况下不到100毫秒,但我想这是不可能的),我可以做什么优化？

更新1: 我将用户输入转换为带有空格的小写英文字符(az).因此'A/b'将转换为'ab'然后进行搜索.

Uodate 2: 我现在意识到我需要额外的东西 - 搜索单词起始子串.

我只是想尝试使用原生Java二进制搜索,希望它总能找到第一次出现.但它并不总是第一次出现,我在这里做错了什么？

import java.util.*;

class BinarySearchWithComparator
{
  public static void main(String[] args)
  {
    // Please scroll down to see 'User' class implementation.
    List<User> l = new ArrayList<User>();
    l.add(new User(10, "A"));
    l.add(new User(10, "A"));
    l.add(new User(10, "A"));

    l.add(new User(20, "B"));
    l.add(new User(20, "B"));
    l.add(new User(20, "B"));
    l.add(new User(20, "B"));
    l.add(new User(20, "B"));
    l.add(new User(20, "B"));
    l.add(new User(20, "B"));


    l.add(new User(30, "C"));
    l.add(new User(30, "C"));
    l.add(new User(30, "C"));
    l.add(new User(30, "C"));

    Comparator<User> c = new Comparator<User>() {
      public int compare(User u1, User u2) …

我试图证明二进制搜索的复杂性.维基百科说,最糟糕的情况是log(n).这意味着:

如果我有16个元素的数组,log(16)是4.我应该有最多4次调用来查找数组中的元素.

我的java代码:

class Main{
      int search(int[] array, int number, int start, int end) {
            System.out.println("Method call");
            int half = (end - start) / 2;

            if (array[start + half] == number) {
                return array[start + half];
            }
            if (array[start + half] < number) {
                return search(array, number, start + half, end);
            } else {
                return search(array, number, start, end - half);
            }
        }

        public static void main(String[] args) {
            int[] array = new int[] { 1, 2, 3, 4, 5, …

我在Elixir中构建了一个二进制搜索,但我最终使用了3个if子句:

if actual == guessed_number, do:

if actual > guessed_number do:

if actual < guessed_number do:

有可能根本不使用条件吗？也许与模式匹配？

我在我的代码中发现了一个令人讨厌的错误,我忘了将一个整数转换为整数str,int然后在一个排序的整数数组中查找它.修复它后,我仍然感到惊讶,这不会导致明确的异常.

这是一个演示:

In [1]: import numpy as np

In [2]: a = np.arange(1000, dtype=int)

In [3]: a.searchsorted('15')
Out[3]: 150

In [4]: a.searchsorted('150')
Out[4]: 150

In [5]: a.searchsorted('1500')
Out[5]: 151

In [6]: a.searchsorted('foo')
Out[6]: 1000

使用float数组这不起作用,提出一个TypeError: Cannot cast array data from dtype('float64') to dtype('<U32') according to the rule 'safe'.

我的主要问题是:为什么这不会导致整数数组的异常？

这是特别令人惊讶的,因为你可以两者都做np.arange(1000, dtype=int).astype(str)和np.arange(1000, dtype=np.float64).astype(str, casting='safe').

附带问题:

• 为什么它转换整个数组而不是参数？
• 为什么搜索字符串转换为'<U32'？

所以,我试图实现二进制搜索算法(尽可能通用,可以适应不同的情况).我在互联网上搜索过这个,有些使用,while (low != high)有些使用,while (low <= high)以及其他一些非常令人困惑的条件.

因此,我开始编写代码来查找大于给定元素的第一个元素.我想知道是否有比这更优雅的解决方案？

主要代码:

#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <stack>
#include <queue>
#include <climits>
#include <set>
#include <cstring>

using namespace std;
int arr1[2000];
int n;
int main (void)
{
    int val1,val2;
    cin>>n;
    for (int i = 0; i < n; i++)
        cin>>arr1[i];
    sort(arr1,arr1+n); 
    cout<<"Enter the value for which next greater element than this value is to be found";   
    cin>>val1;
    cout<<"Enter the value for …

在这种情况下,值匹配并且boolean的值设置为true,但是返回被调用两次并且将值更新为false.任何人都可以建议我在这里缺少什么？

public class BinSearch {

    public static void main(String[] args) {

        BinSearch bin=new BinSearch();
        int arr[]= {2,4,6,8,10,12,14,16};
        boolean b=bin.binSearch(arr,0,arr.length-1,12);
        System.out.println("Number found "+b);

    }

    public  boolean binSearch(int arr[],int low,int high,int val)
    {
        int mid=(low+high)/2;

        if(arr[mid]==val)
        {
            return true;
        }

        else if(arr[mid]>val)
        {
            binSearch(arr,mid+1,high,val);
        }

        else  
        {
            binSearch(arr,low+1,mid,val);
        }

        return false;
    }
}