标签: binary-search

如果数据结构具有随机访问,则标准表示std::binary_search(...)该两个相关函数std::lower_bound(...)和std::upper_bound(...)O(log n).因此,鉴于此,我假设这些算法具有O(log n)性能std::deque(假设其内容由用户保持排序).

然而,似乎内部表示std::deque是棘手的(它被分成块),所以我想知道:O(log n)搜索的要求是否成立std::deque.

我对我正在处理的问题有疑问.我必须按顺序随机播放视频,而不重复播放视频.每个视频仅允许每个播放列表播放一次.每个视频都有一个从0到max_video_count的唯一ID,该id在运行时确定(取决于服务器).

我现在做的是,我创建了一个链接列表,添加了每个视频的唯一ID.比我在0和max_video_count之间随机创建一个随机数,如果数字已经在链表中则进行线性搜索,如果是,我计算一个新数字..再次线性搜索..等等!!

显然,这不是很实用,有时需要很长时间才能找到一个元素.特别是当很多视频播放时.

所以我想,我实现了线性搜索而不是线性搜索,但这让我想到了我必须首先对列表进行排序的问题.所以,我的下一步是思考,我在插入新的unique_id时对列表进行排序,而不是二元搜索.

我知道二进制搜索是O(log n)与O(n)线性搜索相比,这是一个很大的进步.但排序列表也是O(n)因为找到正确的位置我将不得不再做线性搜索.....所以我来解决方案比二进制搜索将是O(log N*n)相比较O(n)线性搜索 - >快速线性搜索.是对的吗？也许我的整个方法都是错的......但我还是想出更好的东西......

我对算法很新,所以如果有人能在这里启发我会很好:-)

问候马库斯

我正在尝试有效地搜索天气,子类实现了一个名为字符串的方法_szMethodName.我可以通过实现获得子类实现的所有方法的数组Method[] _arrClassMethodsList = class.getMethods();.然后,我可以将方法的名称与我要查找的函数的stringName进行比较,以确定天气与否实现该特定方法.目前我在for循环中工作,但随着子类的增长,这会变慢.

对于Loop实现:

for (Method method : class.getMethods()){
       if(method.getName().equals(_szMethodName)){
          //method exists in subclass
          break;
      }
}

方法数组 class.getMethods()按字母顺序排序.(仅限Java> = 7).我希望通过在数组上使用二进制搜索或其他优化而不是使用for循环来利用它.但是,我还没有弄清楚如何在阵列上实现Java的二进制搜索功能.我曾尝试使用比较器或可比较但尚未取得成功.我最近的比较器实现如下,但有一些我尚未解决的错误.

目前尝试使用比较器:

Comparator<Method> c = new Comparator <Method>() {
    public int compare(Method method, String string) {
        return method.getName().compareTo(string);
    }
};

Method[] _arrClassMethodsList = class.getMethods();
int index = Arrays.binarySearch(_arrClassMethodsList, _szMethodName, c);

任何有关如何使这项工作的帮助或示例将不胜感激.谢谢!

我有一个双链表,需要快速插入和删除.我可以在任何一个方向横向移动整个东西以找到插入或移除的位置,但有没有更聪明的方法来找到插入或移除点？首先想到的是二进制搜索,但由于它是一个没有索引(不是数组)的链表,我不知道如何跳转到我的链表.

什么是正确的方法,使插入和删除最快？

在排序数组中,我需要找到第一个整数的位置> =给定的整数(如果数组中不存在这样的整数,则应返回-1).二元搜索的以下修改是否正确解决问题？我使用了不少测试用例来验证功能,但仍想确认.

n =不.数组中的元素

ele =要搜索的整数

int binarySearch(int a[],int n,int ele)
{
  int lower=0;
  int upper=n-1;

  int mid;
  int pos=-1;
  while(lower<=upper)
  {
    mid=(lower+upper)/2;
    if (a[mid]==ele)
    {
        while(mid>=0 && a[mid]==ele)
            mid--;
        return mid+1;
    }
    else if(a[mid]<ele)
        lower=mid+1;
    else
    {
        pos=mid;
        upper=mid-1;
    }
  }
  return pos;
}

在尝试使用BINARY SEARCH方法计算BigInteger的平方根时,我陷入了如何使用两个BigIntegers来满足比较操作的问题.就像,我想检查两个BigInteger变量之间的相等,大于或小于条件.

这是错误的代码片段,粗略地了解我想要执行的内容.任何解决问题的努力都将受到赞赏.

public static BigInteger squareroot(BigInteger bi){
    //BigInteger bkl;
    BigInteger low,high,mid;
low=ONE;
high=bi.add(ZERO);
while(low<=high)
{
    mid =(low.add(high)).divide(new BigInteger("2"));
    if(mid.multiply(mid).equals(bi))
        return mid;
    if(mid.multiply(mid) > bi)
        high = mid -1 ;
    else
        low = mid + 1;
}
return mid;
}

我需要一个二进制搜索功能。

我在标准库中找不到任何函数，该函数将返回找到的项目的索引，如果找不到，将返回比我要查找的项目大的下一个元素的索引的按位补码。

我要寻找的功能是什么？

编辑：我需要将一个项目插入已排序的向量并保持其排序。这就是为什么我需要按位补全索引。

这类似于lower_boundC++,二进制搜索的Javadoc也提到了这一点:"搜索键的索引,如果它包含在数组中;否则,( - (插入点) - 1)."

我已经能够通过一些例子验证它是真的,我很确定它是真的.但是,我无法证明这一点,所以我不确定.

我试图通过矛盾来做某种证明.它沿着这条线运行:如果元素在那里,那么我们必须通过消除包含该元素的范围来错过它.潜在位置和它应该是的位置之间的差距必须是最小的.最后,如果有两个元素,并检查第一个元素,那就是元素,或者元素可能位于的元素后面的元素.

我也试着考虑减少存在元素的情况,没有元素的情况,但这种方法无处可去.我觉得我正在挥舞着证据并抓住吸管.

问题中的陈述是真的吗？如果是这样,你能证明吗？

我正在练习一种采访算法，现在用Go对其进行编码。目的是练习基本的面试算法以及Go的技能。我正在尝试对数字数组进行二进制搜索。

package main

import "fmt"

func main() {
    searchField := []int{2, 5, 8, 12, 16, 23, 38, 56, 72, 91}
    searchNumber := 23

    fmt.Println("Running Program")
    fmt.Println("Searching list of numbers: ", searchField)
    fmt.Println("Searching for number: ", searchNumber)

    numFound := false
    //searchCount not working. Belongs in second returned field
    result, _ := binarySearch2(searchField, len(searchField), searchNumber, numFound)
    fmt.Println("Found! Your number is found in position: ", result)
    //fmt.Println("Your search required ", searchCount, " cycles with the Binary method.")
}

func binarySearch2(a []int, field int, …

我有一个有限数组,其元素只有-1,0或1.我想找到一个数字的第N次出现的索引(比如说0).

我可以遍历整个数组,但我正在寻找更快的方法.我可以考虑使用二进制搜索,但无法对算法进行建模.在这种情况下,如何进行二进制搜索？