Binary search in Java

 Binary Search in Java is a simple and efficient way to find an element in a sorted array. There are two types of Binary Search in Java, Arrays.binarySearch() and Collections.binarySearch(). The former works for arrays of primitive data types like byte, char, double, int, float, short, long and Objects, while the latter works for Collections of objects like ArrayList and LinkedList.

The first type of Binary Search has two declarations, the first one takes an array and the value to be searched, while the second one takes an array, the starting index, the ending index, and the value to be searched. Both return the index of the value in the array, otherwise (-(insertion point + 1)). The insertion point is defined as the index of the first element greater than the value, or the ending index if all elements are less than the value. The range must be sorted prior to calling binarySearch().

Here's an example of implementing the first type of binarySearch() for primitive data types:

java
int arr[] = { 10, 20, 25, 40, 40 }; 
System.out.println(Arrays.binarySearch(arr, 20)); // prints 1
System.out.println(Arrays.binarySearch(arr, 0, 3, 25)); // prints 2
System.out.println(Arrays.binarySearch(arr, 22)); // prints -3

The second type of Binary Search is used for non-primitive types and requires implementing the Comparable or Comparator interface. Here's an example of implementing binarySearch() using a Comparable class:

java
class Point implements Comparable<Point> {
    int x, y;
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
    public int compareTo(Point P) {
        return this.x - P.x;
    }
}

Point arr[] = {
    new Point(10, 20),
    new Point(20, 15),
    new Point(25, 5),
    new Point(40, 100)
};

Point p = new Point(25, 5);
System.out.println(Arrays.binarySearch(arr, p)); // prints 2

Lastly, here's an example of implementing binarySearch() using a Comparator class:

java
class Point {
    int x, y;
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class MyCmp implements Comparator<Point> {
    public int compare(Point p1, Point p2) {
        return p1.x - p2.x;
    }
}

Point arr[] = {
    new Point(10, 20),
    new Point(20, 15),
    new Point(25, 5),
    new Point(40, 100)
};

Point p = new Point(25, 5);
Arrays.sort(arr, new MyCmp());
System.out.println(Arrays.binarySearch(arr, p, new MyCmp())); // prints 2

In summary, Binary Search is a useful algorithm for finding elements in a sorted array or collection, and Java provides easy-to-use methods for its implementation.