标签: binary-search

我有一个5000整数的排序数组.如果随机整数是数组的成员,我能判断多快？一般来说,C和Ruby会很好.

数组值的形式

c * c + 1

where c可以是1到5000之间的任何整数.

例如:

[2, 5, 10, 17, 26, 37, 50 ...]

我正在解决球体在线判断最短路径问题.这段代码给了我麻烦:

int sourceIndex = Arrays.binarySearch(citiesIds,source);

int destinationIndex= Arrays.binarySearch(citiesIds, destination);

double [] distancesFromSource = g.distancesFrom(sourceIndex);

int destinationDistance = (int)distancesFromSource[destinationIndex];

System.out.println(destinationDistance);

我怎么能避免这个NullPointerException？

The complete code:

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package tshpath;



import java.io.*;
import java.util.*;

class Graph {

    private double [][]edges;
    /*el argumento es el número de vértices en este grafo*/
    public Graph(int vertices){

        edges = new double [vertices][vertices];
    }

    /*añade una arista …

任何人都可以解释为什么会这样吗？即.即使在位置7的数组中存在175,array.binarysearch也会返回负值？

请看这个图像:

代码http://www.freeimagehosting.net/uploads/555fef4560.jpg

我有这个Player实现Comparable接口的类.然后,我有一个ArrayList的Player秒.我正试图binarySearch()在Players 列表中找到一个Player,但Java给了我一个" cannot find symbol: method binarySearch(java.util.ArrayList< Player>,Player)".

这个Player类:

class Player implements Comparable {

    private String username;
    private String password;
    Statistics stats;

    //Constructor, creates a new Player with a supplied username
    Player(String name) {
        username = name;
        password = "";
        stats = new Statistics();
    }

    //Accessor method to return the username as a String
    String getName() {
        return username;
    }

    String getPassword() {
        return password; …

一个数组由N个1和0组成,所有1都在0之前.在数组中找不到1的.很明显,使用二进制搜索它是O(log N).是否有算法在O(log(1))时间内执行此操作？

我有两个排序的数组,一个包含因子(数组a),当与另一个数组(数组b)的值相乘时,产生所需的值:

a(idx1) * b(idx2) = value

有了idx2名气,我想找到idx1的a,提供必要获得尽可能接近的因素value成为可能.

我已经看过一些不同的算法(比如这个算法),但我觉得在我的特定情况下它们都会遇到浮点运算的潜在问题.

任何人都可以建议一种避免这种情况的方法吗

我的目的是在循环遍历excel文件时跳过一些预定义的行,如下所示:

int rowIndex = 0;
int[] rowsToBeSkipped = new int[]{1,2,15,16,17,18,31,32,33,34};

while (rowIterator.hasNext()) 
{
    Row row = rowIterator.next();
    if(Arrays.binarySearch(rowsToBeSkipped, rowIndex) == -1){
        System.out.println("true "+rowIndex);
    }else{
        System.out.println("false "+rowIndex);
    }
        rowIndex++;
    }
}

以下是结果:

true 0
false 1
false 2
false 3
false 4
false 5
false 6
false 7
false 8
false 9
false 10
false 11
false 12
false 13
false 14
false 15
false 16
false 17
false 18
false 19
false 20
false 21
false 22
false 23
false …

我在C#中有一个非常大的字符串ArrayList,并且我定期在这个ArrayList中搜索一个字符串.哪一个更快,使用ArrayList.IndexOf()或ArrayList.BinarySearch()？我可以对ArrayList进行排序.

我想从排序单词列表中搜索特定单词.我的单词列表包含100,000个单词.为了提高二进制搜索算法的性能,我想稍微修改一下.例如,如果我想搜索单词"apple"而不是在整个单词列表中应用二进制搜索算法.我将它仅应用于以字母'a'开头的单词.如果我在数组或向量中加载单词列表,我知道我会从索引0开始搜索.问题是我不知道对于以字母'a'开头的单词的最后一个索引是什么.关于如何知道最后一个索引的任何想法？

这是我构建的简单代码片段Arrays.binarySearch.但它正在返回一个我甚至没想到的结果.

    String[] c = {"A", "Z", "B"};
    Arrays.sort(c, new MyNewComparator1()); //Z, B, A
    System.out.println(Arrays.binarySearch(c, "Z")); //0
    System.out.println(Arrays.binarySearch(c, "S")); //-2 based on insertion point
    System.out.println(Arrays.binarySearch(c, "N")); //Unpredicable result we can expect

这是我的自定义比较器

class MyNewComparator1 implements Comparator<String> {
    public int compare(String s1, String s2) {
        return s2.compareTo(s1);
    }
}

我期待的结果 0, -2, Unpredictable

但结果正在回归 -4, -4, -4

有人可以帮我理解为什么它会返回-4所有搜索？

谢谢