标签: binary-search

我正在处理大量数据CSV文件.每个文件包含数百万条记录,每条记录都有一个密钥.记录按其密钥排序.我不想在搜索certian数据时查看整个文件.我见过这个解决方案:用Python阅读巨大的文件

但它建议你在文件上使用相同长度的行 - 在我的情况下不支持.

我想为每行添加一个填充,然后保持固定的行长度,但我想知道是否有更好的方法来做到这一点.

我正在使用python

今天有人问起Lazy Binary Searches.不知道那是什么,我找了它,发现这篇文章:什么是懒二进制搜索？从本质上讲,惰性二进制搜索是一种二元搜索,您首先比较不等式,并且只比较一次的相等性 - 最后.

重点是什么？在什么情况下检查是否A<B容易,但检查是否A=B如此困难,你想尽可能避免它？

是否打开contains方法TreeSet(因为它已经默认排序)比说快HashSet？

我问的原因是Collections.binarySearch如果List被排序的话会很快,所以我想也许TreeSet的contains方法可能是相同的.

在Java中,Arrays.binarySearch始终搜索整个数组.有时阵列的一部分尚未填充.是否有任何函数可以搜索数组的一部分,例如

int binarySearch(int[] a, int end, int value)

是的,我可以使用一个,TreeMap<Integer>但我有很多这些并TreeMap<Integer>使用比int []多几倍的内存.

是的,我当然可以写一个二进制搜索,但考虑到Arrays.binarySearch的存在,似乎我不应该写自己的.

数组中二进制搜索的基本思想很简单,但如果搜索无法找到确切的项目,它可能会返回"近似"索引.(我们有时可能会返回一个值大于或小于搜索值的索引).

为了寻找确切的插入点,似乎在得到大致的位置后,我们可能需要向左或向右"扫描"确切的插入位置,所以,比如说,在Ruby中,我们可以做 arr.insert(exact_index, value)

我有以下解决方案,但部件处理时begin_index >= end_index有点乱.我想知道是否可以使用更优雅的解决方案？

(如果找到完全匹配,此解决方案不关心扫描多个匹配,因此为完全匹配返回的索引可能指向与该值对应的任何索引...但我认为如果它们都是整数,我们a - 1我们知道找到完全匹配后,可以随时搜索,找到左边界,或搜索a + 1右边界.)

我的解决方案

DEBUGGING = true

def binary_search_helper(arr, a, begin_index, end_index)
  middle_index = (begin_index + end_index) / 2
  puts "a = #{a}, arr[middle_index] = #{arr[middle_index]}, " +
           "begin_index = #{begin_index}, end_index = #{end_index}, " +
           "middle_index = #{middle_index}" if DEBUGGING
  if arr[middle_index] == a
    return middle_index
  elsif begin_index >= end_index
    index = [begin_index, end_index].min
    return index if a < arr[index] && index >= 0 …

我在数据结构书中读到了二进制搜索的伪代码,然后我开始编写代码.我写的代码是:

#include <iostream.h>
#include <conio.h>
template <class T>

int BSearch(T x[], const int n, T item)
    {
    int loc, first = 0, found = 0, last = n-1;
        while(first <= last && !found)
        {
            loc = (first + last)/2;
            if(item < x[loc])
                last = loc - 1;
            else if(item > x[loc])
                first = loc + 1;
            else
                found = 1;
         }
      return found;
   }

int main()
    {
    const int n =5;
      int x[n],item;
      cout << "Pls enter " <<n<<" number(s): …

打印出-1我可能会错过这种情况,因为"德国"绝对是在数组中

    public class A 
    {
        static PrintWriter pw = new PrintWriter(System.out, true); 

        public static void main(String[] args) throws IOException 
        {
            String[] a = new String[4];
            a[0]="India";
            a[1]="Italy";
            a[2]="Germany";
            a[3]="India";

            pw.println(Arrays.binarySearch(a, "Germany"));


        }
    }

如何以最好的便携方式对任意排序的数组执行（几乎）无分支的二分搜索？（例如，帮助编译器生成 CMOV 指令的代码对此非常有用。）

“几乎”是指“包含尽可能少的分支”。

假设我有一个对象集合:

List<String> myList = populateMyArrayList();
//Here I am having an ArrayList with 1000 elements

哪种方法更好:

1:Mergesort然后二进制搜索

Collections.sort(myList);
int keyIndex = Collections.binarySearch(myList, key);

2:顺序搜索

for(String s : myList){
   if(s.equals(key)){
      return s;
   }
}

根据要搜索的集合的大小,搜索方法是否应该有所不同？如果是,那么如何决定.

EDIT1:假设我必须多次搜索列表,并且列表中不会添加任何新元素.

编辑2:我本可以去HashSet,但我实际上有一个List<CustomObject>,我可以List根据CustomObject的不同属性多次搜索.所以equals我的CustomObject中没有重写的方法

我有一个带有布尔值的数组。但是像这样的元素序列：首先是true值，然后是false值。例如，

boolean[] booleans = {true, true, true, true, true,
                false, false, false, false, false, false};

所以现在我们有一个带有布尔值的排序数组，true如果true值存在，则从值开始。

任务是找到第一个false元素。
我使用二分搜索算法创建了一个带有搜索方法的类。

public class BinarySearch {

    public static int search(boolean[] array) {

        int low = 0, mid = 0;
        int high = array.length - 1;
        boolean booleanValue;

        while (low <= high) {
            mid = (low + high) >>> 1;
            booleanValue = array[mid];
            if (booleanValue) low = mid + 1;
            else high = mid - …