import java.util.*;
public class Practice {
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");
}
}
/* Hers's My code , here in binSearch method i used the binarySearch method. i know that the binarySearch accepts only if the arrayList is in sorted in ascending order so i revesed it again in order to pass ascending order aList, but my question is if it sees the sorted in ascending order then how it gives the position of the descending order arraylist. for example if i give input 34 78 90 67 then it will sort in descending order 90 78 67 30 . but i have to revese as it again as it does not accept descending order array. so it gets acscending order array list 30 67 78 90 then when i pass the key(suppose 78) it should return the 3rd position ..but no it returns as descending order position 2 why this happens? */
The "hit" of the number 78 in the given example is explained by its position in the middle of the sorted list that is at (list.size()-1)/2, even if binary search in ascending order is applied incorrectly to the list sorted in reverse order.
Searching for the other elements without taking into account the reverseOrder comparator is like a searching in the unsorted list, and therefore the results are undefined according to the documentation.
Simple test to prove this:
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("----");
}
Output:
[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
That is, all indexes for the reversed binary search are correct, while for the ascending binary search there's only one hit.
List<Integer> data = Arrays.asList(20, 98, 33, 12, 78);
Output[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
Similarly, the middle element is luckily hit for ascending search, but the rest of the ascending search results are undefined.
When searching for an element missing in the list, the binarySearch should return appropriate insertion point (which is negative), and appropriate comparator must be selected to provide good results:
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("----");
}
Output:
[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