Rumah >Java >javaTutorial >Java如何实现二进制搜索?
在Java中有两种方法可以进行二进制搜索。
1.Arrays.binarysearch()适用于也可以是原始数据类型的数组。
import java.util.Arrays; public class GFG { public static void main(String[] args) { int arr[] = { 10, 20, 15, 22, 35 }; Arrays.sort(arr); int key = 22; int res = Arrays.binarySearch(arr, key); if (res >= 0) System.out.println(key + " found at index = " + res); else System.out.println(key + " Not found"); key = 40; res = Arrays.binarySearch(arr, key); if (res >= 0) System.out.println(key + " found at index = " + res); else System.out.println(key + " Not found"); } }
输出:
22 found at index = 3 40 Not found
2.Collections.binarysearch()适用于对象集合,如ArrayList和LinkedList。
import java.util.List; import java.util.ArrayList; import java.util.Collections; public class GFG { public static void main(String[] args) { List<Integer> al = new ArrayList<Integer>(); al.add(1); al.add(2); al.add(3); al.add(10); al.add(20); int key = 10; int res = Collections.binarySearch(al, key); if (res >= 0) System.out.println(key + " found at index = " + res); else System.out.println(key + " Not found"); key = 15; res = Collections.binarySearch(al, key); if (res >= 0) System.out.println(key + " found at index = " + res); else System.out.println(key + " Not found"); } }
输出:
10 found at index = 3 15 Not found
如果输入没有排序怎么办?
如果未对输入列表进行排序,则结果未定义。
如果有重复怎么办?
如果有重复,则无法保证找到哪一个。
Collections.binarySearch如何为LinkedList工作?
此方法在log(n)时间内运行,用于“随机访问”列表,如ArrayList。如果指定的列表没有实现RandomAccess接口并且很大,则此方法将执行基于迭代器的二进制搜索,该搜索执行O(n)链接遍历和O(log n)元素比较。
两个函数返回的负值的重要值是多少?
该函数返回搜索键的索引(如果它包含在数组中); 否则,( - (插入点) - 1)。插入点定义为键将插入到数组中的点:第一个元素的索引大于键,或者如果数组中的所有元素都小于指定键,则为a.length。请注意,当且仅当找到密钥时,这可以保证返回值> = 0。
如何在Java中实现我们自己的二进制搜索?
class BinarySearch { int binarySearch(int arr[], int l, int r, int x) { if (r>=l) { int mid = l + (r - l)/2; if (arr[mid] == x) return mid; if (arr[mid] > x) return binarySearch(arr, l, mid-1, x); return binarySearch(arr, mid+1, r, x); } return -1; } public static void main(String args[]) { BinarySearch ob = new BinarySearch(); int arr[] = {2,3,4,10,40}; int n = arr.length; int x = 10; int result = ob.binarySearch(arr,0,n-1,x); if (result == -1) System.out.println("Element not present"); else System.out.println("Element found at index " + result); } }
输出:
Element found at index 3
相关推荐:《Java教程》
本篇文章就是关于Java实现二进制搜索的方法介绍,希望对需要的朋友有所帮助!
Atas ialah kandungan terperinci Java如何实现二进制搜索?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!