Java 使用二分搜索的程序搜索ArrayList元素

搜索是一种从一组随机元素中找到特定信息的排序过程。在线性数据结构中，有两种类型的搜索过程-

• 线性搜索

• 二分搜索

线性搜索是一种简单的搜索方法，通过这种方法可以顺序地从数据源中找到元素。对于这个搜索过程，最佳执行时间为1，最差执行时间始终被认为是n。

二分搜索是一种特定键元素从多个元素的库存中搜索的过程，它遵循分而治之的方法。在这个搜索过程中，算法以重复的方式运行。搜索过程的区间将在这里减半。

在本文中，我们将学习如何使用Java中的二分搜索方法来搜索ArrayList。

什么是二分搜索以及它如何在Java中工作

• 二分搜索是一种在数据集合中搜索目标元素的技术。

• 二进制数据搜索是最可接受和使用的技术。它比线性搜索快。

• 递归二进制搜索是一种递归技术，整个过程将一直运行到找到目标元素为止。

• 一般来说，二分搜索通过将数组分成一些部分来执行。

• 当内存空间不足时，我们可以使用此进程。

步骤

• 步骤1-开始。

• 步骤2-按升序对数组进行排序。

• 步骤3-将低索引设置为第一个元素。

• 步骤4-将高索引设置为最后一个元素。

• 步骤5-使用低或高指示设置中间索引的平均值。

• 步骤6-如果目标元素在中间。返回中间值。

• 步骤7-如果目标元素小于中间元素，则将高设置为中间值-1。

• 步骤8-如果目标元素大于中间元素，则将低设置为中间值+1。

• 步骤9-重复，直到满足搜索条件。

• 步骤10-否则，清楚的话元素不存在。

二分搜索的语法 – 通过迭代

mid = (low + high)/2
    if (x == arr[mid])
        return mid
    else if (x > arr[mid]) 
        low = mid + 1
    else                       
        high = mid - 1

二分搜索的语法 – 通过递归

binarySearch(arr, z, low, high)
    if low > high
        return False 
    else
        mid = (low + high) / 2 
        if z == arr[mid]
            return mid
        else if z > arr[mid]        
            return binarySearch(arr, z, mid + 1, high)
        else                               
            return binarySearch(arr, z, low, mid - 1)

有两种不同的方法可以使用二分查找在ArrayList中查找元素。上面我们已经提到了这些方法的语法，以便在Java环境中更好地了解二分查找的过程。

方法

• 方法1 – 一般的二分查找程序

• 方法2 – 使用迭代的二分查找

• 方法3 – 使用递归的二分查找

方法1：一般的二分查找程序

在这段Java代码中，我们试图让您了解在Java环境中二分查找程序的实际工作原理。希望您能理解这里提到的整个过程和算法。

示例1

import java.io.*;
import java.util.*;

public class binarysearchbyrdd {
   static boolean search(int key, ArrayList<Integer> B){
      int low = 0;
      int high = B.size() - 1;
      while (low <= high) {
         int mid = low + (high - low) / 2;
         if (B.get(mid) == key) {
            return true;
         }
         else if (B.get(mid) < key) {
            low = mid + 1;
         } else {
            high = mid - 1;
         }
      }
      return false;
   }
   public static void main(String[] args){
      ArrayList<Integer> R = new ArrayList<>();
      R.add(10);
      R.add(16);
      R.add(07);
      R.add(01);
      R.add(97);
      R.add(22);
      R.add(23);
      R.add(9);
      int key = 19;
      boolean check = search(key, R);
      System.out.println(check);
      int key7 = 2;
      boolean check7 = search(key7, R);
      System.out.println(check7);
   }
}

输出

false
false

方法2：使用迭代法进行二分查找

使用迭代法进行二分查找（过程）-

• 给定要与要搜索的元素进行比较的值。

• 如果匹配则返回该值。

• 如果值大于中间元素，则转向右子数组。

• 如果值小于中间元素，则转向左子数组。

• 如果没有返回值，则结束该过程。

示例2

import java.io.*;
import java.util.*;

public class BinarytpSearch {
    int binarytpSearch(ArrayList<Integer> arr, int x) {
        int left = 0, right = arr.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr.get(mid) == x)
                return mid;
            if (arr.get(mid) < x)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return -1;
    }
    public static void main(String args[]) {
        BinarytpSearch ob = new BinarytpSearch();

        ArrayList<Integer> arr = new ArrayList<Integer>();

        arr.add(16);
        arr.add(10);
        arr.add(97);
        arr.add(07);
        arr.add(10);
        arr.add(2001);
        arr.add(2022);

        int x = 10;
        System.out.println("The elements of the arraylist here are: "+arr);

        int result = ob.binarytpSearch(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 here are: [16, 10, 97, 7, 10, 2001, 2022]
The Element 10 is found at index 4

方法3：使用递归的二分查找

使用递归的二分查找（过程）-

• 将要搜索的元素与中间元素进行比较。

• 如果匹配，则返回中间索引。

• 否则，如果数字大于中间元素，则继续搜索右子数组。

• 否则，递归搜索左半部分。

示例3

import java.io.*;
import java.util.*;

public class Binary0Search {
    int binary0Search(ArrayList<Integer> arr, int l1, int r2, int x7){
        if (r2 >= l1){
            int mid = l1 + (r2 - l1) / 2;
            if (arr.get(mid) == x7)
                return mid;
            if (arr.get(mid) > x7)
                return binary0Search(arr, l1, mid - 1, x7);
            return binary0Search(arr, mid + 1, r2, x7);
        }
        return -1;
    }
    public static void main(String args[]){
        Binary0Search ob = new Binary0Search();

        ArrayList<Integer> arr = new ArrayList<Integer>();
        arr.add(16);
        arr.add(10);
        arr.add(97);
        arr.add(07);
        arr.add(10);
        arr.add(2001);
        arr.add(2022);

        int n = arr.size();
        int x7 = 10;
        System.out.println("The elements present in the arraylist are: "+arr);

        int result = ob.binary0Search(arr,0,n-1,x7);

        if (result == -1)
            System.out.println("Element not present here, Sorry!");
        else
            System.out.println("The Element " + x7 + " is found at "+ "index number" + result);
    }
}

输出

The elements present in the arraylist are: [16, 10, 97, 7, 10, 2001, 2022]
The Element 10 is found at index number4

结论

在本文中，我们学习了如何在Java中进行二分查找。通过使用迭代和递归二分查找，我们根据算法构建了一些Java代码。希望这能帮助您更好地理解如何在Java环境中使用二分查找搜索ArrayList元素。