使用二分搜索法搜索 ArrayList 元素的 Java 程序
搜索是一种排序过程,用于从一组随机元素中查找特定信息。在线性数据结构中,有两种类型的搜索过程 -
线性搜索
二分搜索
线性搜索是一种简单的搜索方法,通过该方法我们可以按顺序从数据源中找到元素。对于此搜索过程,最佳执行时间为 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 元素。
相关文章
有用资源
java 参考教程 - 该教程包含有关 java 的更多信息:https://www.cainiaomax.com/java/

