資料結構
網路
關係資料庫管理系統
作業系統
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次瀏覽
