java 对按降序排序的 int 数组使用二分搜索
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/28283693/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Use a Binary Search on an int array sorted in descending order
提问by Ryuk
import java.util.*;
import java.io.*;
import java.util.Arrays;
import java.util.Collections;
import org.apache.commons.lang3.ArrayUtils;
@SuppressWarnings("unused")
public class Tester {
public static void main(String args[]){
int i[] = {-7, 15, 21, 22, 43, 49, 51, 67, 81, 84, 89, 95, 97};
ArrayUtils.reverse(i);
System.out.println(binarySearch(i, 22));
System.out.println(binarySearch(i, 89));
System.out.println(binarySearch(i, -100));
System.out.println(binarySearch(i, 72));
System.out.println(binarySearch(i, 102));
}
private static int binarySearch(int a[], int srchVal){
int lb = 0;
int ub = a.length - 1;
while(lb <= ub){
int mid = (lb + ub)/2;
if(a[mid] == srchVal){
return mid;
}
else if(srchVal > a[mid]){
lb = mid + 1;
}
else{
ub = mid - 1;
}
}
return -1;
}
}
For an assignment in class I need to modify the BinarySearch method so that it will work properly with the reversed array. But I can't figure out how I'm supposed to modify it.
对于类中的分配，我需要修改 BinarySearch 方法，以便它可以与反向数组一起正常工作。但是我不知道我应该如何修改它。
回答by rgettman
If the array is sorted in descending order, binary search can still work if you reverse the sense of all value comparisons performed by the search algorithm.
如果数组按降序排序，如果您反转搜索算法执行的所有值比较的意义，二分搜索仍然可以工作。
The equals case is still fine, but you can reverse the comparison made in the else ifto a <. The elsedoesn't need to be modified, because the else ifchange means the elseblock will now represent the >condition.
equals 的情况仍然可以，但您可以将在else ifa 中进行的比较颠倒过来<。在else不需要进行修改，因为else if变化意味着该else块现在将代表>条件。
回答by Willem Van Onsem
Binary search makes the assumption the data is ordered. If that's the case, than one knows if the value of the selected index (mid) is less than the value, the value must be in the range 0..mid-1and vice versa.
二分搜索假设数据是有序的。如果是这种情况，那么人们就会知道所选索引 ( mid) 的值是否小于该值，该值必须在范围内0..mid-1，反之亦然。
In case the array is ordered in reverse, one knows that if the value is less, then one must search in the second part. The only thing you must modify is the condition in the else if:
如果数组是倒序排列的，人们知道如果值较小，则必须在第二部分中搜索。您唯一必须修改的是 中的条件else if：
else if(srchVal < a[mid]){ //change < to >
lb = mid + 1;
}
That said, one better makes the method a bit more generic so one can make the comparator more generic as well:
也就是说，最好使方法更通用一点，这样也可以使比较器更通用：
private static<T> int binarySearch(T[] a, Comparator<T> c, T srchVal){
int lb = 0;
int ub = a.length - 1;
while(lb <= ub){
int mid = (lb + ub)/2;
int ci = c.compare(a[mid],srchVal);
if(ci == 0){
return mid;
}
else if(ci < 0){
lb = mid + 1;
}
else{
ub = mid - 1;
}
}
return -1;
}
In case you provide a reversed array, you only need to provide a Comparator<T>that returns -valwith valthe comparator for the original array.
如果你提供了一个相反的数组，你只需要提供一个Comparator<T>即返回-val与val比较原始阵列。
回答by Nikhil Kumar vats
There is a hack: 1) Reverse whole array so that now it is increasing order array. 2) Apply binary search and then find suitable index. 3) n-index will be your answer.
有一个技巧：1）反转整个数组，以便现在它是递增顺序数组。2) 应用二分查找，然后找到合适的索引。3) n-index 将是你的答案。
回答by Ram Repaka
Just change srchVal > a[mid] condition to srchVal < a[mid]
只需将 srchVal > a[mid] 条件更改为 srchVal < a[mid]
import java.util.*;
import java.io.*;
import java.util.Arrays;
import java.util.Collections;
public class HelloWorld{
private static int binarySearch(int a[], int srchVal){
int lb = 0;
int ub = a.length - 1;
while(lb <= ub){
int mid = (lb + ub)/2;
if(a[mid] == srchVal){
return mid;
}
else if(srchVal < a[mid]){
lb = mid + 1;
}
else{
ub = mid - 1;
}
}
return -1;
}
public static void main(String []args){
int i[] = {97,95,89,84,81,67,51,49,43,22,21,15,-7};
System.out.println(binarySearch(i, 22));
System.out.println(binarySearch(i, 89));
System.out.println(binarySearch(i, -100));
System.out.println(binarySearch(i, 72));
System.out.println(binarySearch(i, 102));
}
}
回答by Abhijeet Ankush
You can pass a reverse comparator in the binary search when you want to run the binary search in an array which is sorted in descending order. Example:
当您想在按降序排序的数组中运行二进制搜索时，您可以在二进制搜索中传递一个反向比较器。例子：
Integer [] arr = new Integer[]{5,6,2,9,7};
Arrays.sort(arr, Collections.reverseOrder()); //sorting the array in descending order
Arrays.binarySearch(arr, 2, Comparator.reverseOrder()) // Searches of for 2 in the array.
The above function will return 4 which is the index of 2 in reverse sorted array. It also works as usual if the element is not present in the array. For example, if you search of value 3, it will return -5. (-insertion index -1) Check thisfor details.
上面的函数将返回 4，它是反向排序数组中 2 的索引。如果元素不存在于数组中，它也照常工作。例如，如果您搜索值 3，它将返回 -5。(-insertion index -1)详情请查看这里。
Thanks
谢谢
回答by Lajos Arpad
Binary searches work on sorted sets. Your code assumes that the order is ascending, yet, it is the inverse. As a result, you need to invert the condition:
二分搜索适用于已排序的集合。您的代码假定顺序是升序，但它是相反的。因此，您需要反转条件：
while(lb > ub){
On more general terms, you could be agnostic about the direction:
用更一般的术语来说，您可能对方向不可知：
private static int binarySearch(int a[], int srchVal, boolean isAscending){
int lb = 0;
int ub = a.length - 1;
while((lb <= ub) == isAscending){
int mid = (lb + ub)/2;
if(a[mid] == srchVal){
return mid;
}
else if(srchVal > a[mid]){
lb = mid + 1;
}
else{
ub = mid - 1;
}
}
return -1;
}
and use ascending order by default:
并默认使用升序：
private static int binarySearch(int a[], int srchVal){
return binarySearch(a, srchVal, true);
}
but descending in your case
但在你的情况下下降
public static void main(String args[]){
int i[] = {-7, 15, 21, 22, 43, 49, 51, 67, 81, 84, 89, 95, 97};
ArrayUtils.reverse(i);
System.out.println(binarySearch(i, 22), false);
System.out.println(binarySearch(i, 89), false);
System.out.println(binarySearch(i, -100), false);
System.out.println(binarySearch(i, 72), false);
System.out.println(binarySearch(i, 102), false);
}
