java 中的 BinarySearch 方法

Question

导入java.util.*;

public class练习{

static ArrayList<Integer> populateList(Scanner sc , ArrayList<Integer> al){
    String l = sc.nextLine();
    String arr[] = l.trim().split("\s++");
    for(int i = 0; i<arr.length; i++){ 
        al.add(Integer.parseInt(arr[i]));
    }
    return al;
}
static void displayList(String s , ArrayList<Integer> al){
    System.out.print(s+": ");
    for(int i = 0; i<al.size(); i++){
        System.out.print(al.get(i)+" " );
    }
    System.out.println("");
}
static  ArrayList<Integer> sortListDesc(ArrayList<Integer> al ){
     Collections.sort(al,Collections.reverseOrder());
    return al;
}

static int binSearch(ArrayList<Integer> al , int key){
    
    int index = Collections.binarySearch(al,key,Collections.reverseOrder());
    return index+1;
}


public static void main(String[] args) {
    int key, index;
    Scanner sc = new Scanner(System.in); // Handle inputs
     
     // Create a list of Integers
     ArrayList<Integer> al = new ArrayList<Integer>();
    
     // Enter few numbers in a line and populate the list
     populateList( sc, al ); 
     
     // Display list
     displayList( "Original List", al );
     
     // Sort list in descending order
     sortListDesc( al );
     
     // Display sorted list
     displayList( "Sorted List", al );
     
     // Input key
     key = sc.nextInt();
     
     // Perform binary search for key in al
     index = binSearch(al, key);
     if (index >= 0)
    System.out.println("Position: " + index);
     else
    System.out.println("Not found");
       }
    }

/* 她的我的代码，在 binSearch 方法中我使用了 binarySearch 方法。我知道 binarySearch 仅在 arrayList 按升序排序时才接受，所以我再次修改它以传递升序 aList，但我的问题是如果它看到按升序排序，那么它如何给出降序的位置订购数组列表。例如，如果我输入 34 78 90 67 那么它将按降序排序 90 78 67 30 。但我必须再次修改它，因为它不接受降序数组。所以它得到升序数组列表 30 67 78 90 然后当我传递密钥时（假设 78）它应该 return 第 3 个位置..但不是 returns 作为降序位置 2 为什么会发生这种情况？ */

Answer 1

给定示例中数字 78 的“命中”由其在 (list.size()-1)/2 排序列表中间的位置来解释，即使二进制搜索升序错误地应用于按反向顺序排序的列表。

在不考虑 reverseOrder 比较器的情况下搜索其他元素就像在未排序的列表中搜索，因此根据文档搜索 results are undefined。

证明这一点的简单测试：

输入数据：偶数长度= 4

List<Integer> data = Arrays.asList(20, 98, 33, 78);
data.sort(Collections.reverseOrder());
System.out.println(data);

for (int x : data) {
    int ix = Collections.binarySearch(data, x); // ascending is incorrect
    System.out.println("ix["+x+"]=" + ix);
    
    int ix2 = Collections.binarySearch(data, x, Collections.reverseOrder());
    System.out.println("reverse ix["+x+"]=" + ix2);
    System.out.println("----");
}

输出：

[98, 78, 33, 20]
ix[98]=-5
reverse ix[98]=0
----
ix[78]=1
reverse ix[78]=1
----
ix[33]=-1
reverse ix[33]=2
----
ix[20]=-1
reverse ix[20]=3

也就是说，反向二分查找的所有索引都是正确的，而升序二分查找只有一个命中。

输入数据：奇数长度List<Integer> data = Arrays.asList(20, 98, 33, 12, 78); 输出

[98, 78, 33, 20, 12]
ix[98]=-6
reverse ix[98]=0
----
ix[78]=-6
reverse ix[78]=1
----
ix[33]=2
reverse ix[33]=2
----
ix[20]=-1
reverse ix[20]=3
----
ix[12]=-1
reverse ix[12]=4

同样，升序搜索幸运命中中间元素，但其余升序搜索结果未定义。

在列表中搜索缺失的元素时，binarySearch应该return适当的插入点（为负数），并且必须选择适当的比较器来提供好成绩：

List<Integer> data = Arrays.asList(20, 98, 33, 12, 78);
data.sort(Collections.reverseOrder());
System.out.println(data);

List<Integer> data = Arrays.asList(20, 98, 33, 12, 78);
data.sort(Collections.reverseOrder());
System.out.println(data);

for (int i = 0, n = data.size(); i <= n; i++) {
    int x = i < n ? data.get(i) + 2 : data.get(i - 1) - 2;
    int ix = Collections.binarySearch(data, x);
    System.out.println("ix["+x+"]=" + ix);
    
    int ix2 = Collections.binarySearch(data, x, Collections.reverseOrder());
    System.out.println("reverse ix["+x+"]=" + ix2);
    System.out.println("----");
}

输出：

[98, 78, 33, 20, 12]
ix[100]=-6
reverse ix[100]=-1
----
ix[80]=-6
reverse ix[80]=-2
----
ix[35]=-6
reverse ix[35]=-3
----
ix[22]=-1
reverse ix[22]=-4
----
ix[14]=-1
reverse ix[14]=-5
----
ix[10]=-1
reverse ix[10]=-6

java 中的 BinarySearch 方法

BinarySearch method in java

java

arraylist

binary-search-tree