How to implement binary search in Java?

There are two ways to do binary search in Java.

1.Arrays.binarysearch()Applies to arrays that can also be primitive data types.

import java.util.Arrays; 
  
public class GFG { 
    public static void main(String[] args) 
    { 
        int arr[] = { 10, 20, 15, 22, 35 }; 
        Arrays.sort(arr); 
  
        int key = 22; 
        int res = Arrays.binarySearch(arr, key); 
        if (res >= 0) 
            System.out.println(key + " found at index = " 
                                                  + res); 
        else
            System.out.println(key + " Not found"); 
  
        key = 40; 
        res = Arrays.binarySearch(arr, key); 
        if (res >= 0) 
            System.out.println(key + " found at index = " 
                                                  + res); 
        else
            System.out.println(key + " Not found"); 
    } 
}

Output:

22 found at index = 3
40 Not found

2.Collections.binarysearch()Applies to object collections, such as ArrayList and LinkedList.

import java.util.List; 
import java.util.ArrayList; 
import java.util.Collections; 
   
public class GFG 
{ 
    public static void main(String[] args) 
    { 
        List<Integer> al = new ArrayList<Integer>(); 
        al.add(1); 
        al.add(2); 
        al.add(3); 
        al.add(10); 
        al.add(20); 
   
        int key = 10; 
        int res = Collections.binarySearch(al, key); 
        if (res >= 0) 
            System.out.println(key + " found at index = " 
                                                 + res); 
        else
            System.out.println(key + " Not found"); 
  
        key = 15; 
        res = Collections.binarySearch(al, key); 
        if (res >= 0) 
            System.out.println(key + " found at index = "
                                                  + res); 
        else
            System.out.println(key + " Not found"); 
    } 
}

Output:

10 found at index = 3
15 Not found

What if the input is not sorted?
If the input list is not sorted, the result is undefined.

What to do if there are duplicates?
If there are duplicates, there is no guarantee which one will be found.

How does Collections.binarySearch work for LinkedList?
This method runs in log(n) time and is used for "random access" lists such as ArrayList. If the specified list does not implement the RandomAccess interface and is large, this method performs an iterator-based binary search that performs O(n) link traversal and O(log n) element comparison.

What is the significance of the negative values ​​returned by the two functions?
This function returns the index of the search key (if it is contained in the array); otherwise, (-(insertion point)-1). The insertion point is defined as the point at which the key will be inserted into the array: the index of the first element is greater than the key, or a.length if all elements in the array are less than the specified key. Note that this guarantees a return value >= 0 if and only if the key is found.

How to implement our own binary search in Java?

class BinarySearch 
{ 
    int binarySearch(int arr[], int l, int r, int x) 
    { 
        if (r>=l) 
        { 
            int mid = l + (r - l)/2; 
            if (arr[mid] == x) 
               return mid; 

            if (arr[mid] > x) 
               return binarySearch(arr, l, mid-1, x); 
 
            return binarySearch(arr, mid+1, r, x); 
        } 

        return -1; 
    } 
 
    public static void main(String args[]) 
    { 
        BinarySearch ob = new BinarySearch(); 
        int arr[] = {2,3,4,10,40}; 
        int n = arr.length; 
        int x = 10; 
        int result = ob.binarySearch(arr,0,n-1,x); 
        if (result == -1) 
            System.out.println("Element not present"); 
        else
            System.out.println("Element found at index " +  
                                                 result); 
    } 
}

Output:

Element found at index 3

Related recommendations: "Java Tutorial"

This article is an introduction to the method of implementing binary search in Java , I hope it will be helpful to friends in need!

The above is the detailed content of How to implement binary search in Java?. For more information, please follow other related articles on the PHP Chinese website!