数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究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 - 使用递归的二分查找
通用二分查找程序
在此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);
}
}
输出
The elements of the arraylist here are: [16, 10, 97, 7, 10, 2001, 2022] The Element 10 is found at index 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);
}
}
输出
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元素。
444次浏览
