Java程序 对ArrayList进行二分查询

ArrayList类是集合框架的一部分，存在于java.util包中。它在java中为我们提供了可调整大小的或动态的数组。它比标准数组慢，但在一些程序中，我们需要提出更简洁、更短的代码，并且需要对数组进行大量的操作，这时就会有帮助。

在一个排序的数组中搜索一个元素最有效的算法是二进制搜索算法。在这篇文章中，我们将使用Java ArrayList来实现这一点。

步骤:

有三种方法可以在java ArrayList上实现二进制搜索，下面列出了概念，然后是一个java例子的实现部分。

1.迭代二进制搜索（使用循环的正常二进制搜索）。
2.递归二进制搜索（使用递归的二进制搜索）。
3.使用java集合的内置binarySearch方法。

方法1：迭代式二进制搜索

在这种方法中，我们在一次比较后忽略了一半的元素。由于数组是排序的。

• 将要搜索的给定值与中间元素进行比较。
• 如果它与中间元素匹配，我们就返回x。
• 如果它大于中间的元素，那么对右边的子数组做同样的处理.也就是说，数组的大小被减少到一半，我们剩下要比较的是右边的子数组。
• 如果它小于中间的元素，那么就对左边的子数组做同样的处理，也就是说，数组的大小被减少到一半，我们剩下要比较的是左边的子数组。
• 如果我们没有返回任何东西，但我们的搜索结束了，那么返回-1，这意味着该元素不存在于该数组中。

// Java program to print binary search over an ArrayList
 
import java.io.*;
import java.util.*;
 
class BinarySearch
{
    // Returns index of x if it is present in arr[],
    // else return -1
    int binarySearch(ArrayList<Integer> arr, int x)
    {
        int left = 0, right = arr.size() - 1;
       
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
   
            // Check if x is present at mid
            if (arr.get(mid) == x)
                return mid;
   
            // If x greater, ignore left half
            if (arr.get(mid) < x)
                left = mid + 1;
   
            // If x is smaller, ignore right half
            else
                right = mid - 1;
        }
   
        // if we reach here, then element was
        // not present
        return -1;
    }
   
    // Driver method to test above
    public static void main(String args[])
    {
        BinarySearch ob = new BinarySearch();
       
        ArrayList<Integer> arr = new ArrayList<Integer>();
       
        arr.add(5);
        arr.add(10);
        arr.add(15);
        arr.add(20);
        arr.add(25);
        arr.add(30);
        arr.add(35);
       
        int x = 10;
       
        // Printing elements of array list
        System.out.println("The elements of the arraylist are: "+arr);
       
        int result = ob.binarySearch(arr, x);
       
        if (result == -1)
            System.out.println("Element not present");
       
        else
            System.out.println("The Element " + x + " is found at "
                               + "index " + result);
    }
}

输出

The elements of the arraylist are: [5, 10, 15, 20, 25, 30, 35]
The Element 10 is found at index 1

方法2：递归二进制搜索

• 将被搜索的元素t(x)与中间元素进行比较。
• 如果x与中间元素匹配，我们就返回中间索引。
• 否则 如果x大于中间元素，那么x只能位于中间元素之后的右半边子阵列中。所以我们对右半部分进行递归。
• 否则（x较小），左半边重复进行。

// Java implementation of recursive Binary Search
 
import java.io.*;
import java.util.*;
 
class BinarySearch
{
    // Returns index of x if it is present in arr[l..
    // r], else return -1
   
    int binarySearch(ArrayList<Integer> 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.get(mid) == x)
                return mid;
 
            // If element is smaller than mid, then
            // it can only be present in left subarray
            if (arr.get(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();
       
        ArrayList<Integer> arr = new ArrayList<Integer>();
        arr.add(5);
        arr.add(10);
        arr.add(15);
        arr.add(20);
        arr.add(25);
        arr.add(30);
        arr.add(35);
       
        int n = arr.size();
       
        // We will find x inside the arraylist
        int x = 10;
       
        // Printing elements of array list
        System.out.println("The elements of the arraylist are: "+arr);
       
        int result = ob.binarySearch(arr,0,n-1,x);
       
        if (result == -1)
            System.out.println("Element not present");
        else
            System.out.println("The Element " + x + " is found at "
                               + "index " + result);
    }
}

输出

The elements of the arraylist are: [5, 10, 15, 20, 25, 30, 35]
The Element 10 is found at index 1

方法3：使用集合类的内置二进制搜索方法

在这个方法中，我们只是调用collection框架的binarySearch()方法，并将我们排序后的ArrayList和要搜索的值解析到该方法中，如果存在元素，这将返回该元素的索引，否则返回1。

// Java program to demonstrate the searching of
// an element in ArrayList using binarySearch()
// of Collections class
 
import java.util.ArrayList;
import java.util.Collections;
 
public class BinarySearch {
   
    public static void main(String[] args)
    {
        ArrayList<Integer> arr = new ArrayList<Integer>();
       
        arr.add(5);
        arr.add(10);
        arr.add(15);
        arr.add(20);
        arr.add(25);
        arr.add(30);
        arr.add(35);
       
        // Initializing the key to be found.
        int val = 10;
       
        // Printing elements of array list
        System.out.println("The elements of the arraylist are: "+arr);
       
        // Implementing the built-in binarySearch method from collections
        int result = Collections.binarySearch(arr,val);
       
        if (result == -1)
            System.out.println("Element not present");
        else
            System.out.println("The Element " + val + " is found at "
                               + "index " + result);
    }
}

输出

The elements of the arraylist are: [5, 10, 15, 20, 25, 30, 35]
The Element 10 is found at index 1

时间复杂度 : O(logn)

辅助空间 :O(1)，因为它使用的是常量变量