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

javaobject oriented programmingprogramming更新于 2024/3/15 17:16:17

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

  • 线性搜索

  • 二分搜索

线性搜索是一种简单的搜索方法,通过该方法我们可以按顺序从数据源中找到元素。对于此搜索过程,最佳执行时间为 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 - 使用递归的二分搜索

通用二分搜索程序

在此 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

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);
	}
}

输出

此处数组列表的元素为:[16, 10, 97, 7, 10, 2001, 2022]
元素 10 位于索引 4

使用递归进行二分查找

使用递归进行二分查找(过程)−

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

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

  • 否则,数字大于中间元素,则将遵循右子数组。

  • 否则,递归左半部分。

示例 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);
	}
}

输出

arraylist 中存在的元素为:[16, 10, 97, 7, 10, 2001, 2022]
元素 10 位于索引号 4

结论

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


相关文章


有用资源