Java 二分查找

二分查找是当输入被排序时应用的搜索技术之一，因为这里我们专注于寻找中间的元素，作为参考框架，是否向左或向右走，因为元素已经被排序了。这种搜索有助于优化每一次迭代的搜索技术，被称为二分查找，读者对它确实有压力，因为它是间接应用于解题的。现在你一定在想，如果输入没有被排序，那么结果就无法确定。

注意： 如果有重复的，不能保证哪一个会被找到。

现在让我们来坚持一下这两个函数返回的负值的重要价值？

该函数返回一个搜索键的索引，如果它包含在数组中；否则，返回（-（插入点）-1）。插入点被定义为将钥匙插入数组的点：第一个大于钥匙的元素的索引，如果数组中的所有元素都小于指定的钥匙，则为a.length。请注意，这保证了当且仅当键被找到时，返回值将>=0。

在Java中实现二分查找

// Java implementation of recursive Binary Search
class BinarySearch
{
    // Returns index of x if it is present in arr[l..
    // r], else return -1
    int binarySearch(int arr[], int l, int r, int x)
    {
        if (r>=l)
        {
            int mid = l + (r - l)/2;
  
            // If the element is present at the
            // middle itself
            if (arr[mid] == x)
               return mid;
  
            // If element is smaller than mid, then
            // it can only be present in left subarray
            if (arr[mid] > x)
               return binarySearch(arr, l, mid-1, x);
  
            // Else the element can only be present
            // in right subarray
            return binarySearch(arr, mid+1, r, x);
        }
  
        // We reach here when element is not present
        //  in array
        return -1;
    }
  
    // Driver method to test above
    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);
    }
}

输出

Element found at index 3

提示： 极客们一定想知道是否有类似 lower_bound() 或 upper_bound() 的函数，只是可能在C++ STL中找到。所以直接的答案是，直到Java 9才有这个函数，后来才加入。

Java中二分查找的类型

有两种方法可以在Java中进行二分查找

Arrays.binarysearch
Collections.binarysearch()

类型1： Arrays.binarysearch()

它适用于也可以是原始数据类型的数组。

例子

// Java Program to demonstrate working of binarySearch()
// Method of Arrays class In a sorted array
 
// Importing required classes
import java.util.Arrays;
 
// Main class
public class GFG {
 
    // Main driver method
    public static void main(String[] args)
    {
        // Declaring an integer array
        int arr[] = { 10, 20, 15, 22, 35 };
 
        // Sorting the above array
        // using sort() method od Arrays class
        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");
    }
}

输出

22 found at index = 3
40 Not found

现在让我们看看Collections.binarySearch()对LinkedList是如何工作的。基本上，正如上面所讨论的，对于像ArrayList这样的 “随机访问 “列表，该方法的运行时间为log(n)。如果指定的列表没有实现RandomAccess接口，并且规模较大，该方法将进行基于迭代器的二分查找，执行O(n)的链接遍历和O(log n)的元素比较。

类型2： Collections.binarysearch()

它适用于对象集合，如ArrayList和LinkedList。

例子

// Java Program to Demonstrate Working of binarySearch()
// method of Collections class
 
// Importing required classes
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
 
// Main class
public class GFG {
    // Main driver method
    public static void main(String[] args)
    {
        // Creating an empty ArrayList of integer type
        List<Integer> al = new ArrayList<Integer>();
 
        // Populating the Arraylist
        al.add(1);
        al.add(2);
        al.add(3);
        al.add(10);
        al.add(20);
 
        // 10 is present at index 3
        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");
    }
}