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实现二进制搜索的方法介绍，希望对需要的朋友有所帮助！

以上就是Java如何实现二进制搜索？的详细内容，更多内容请关注技术你好其它相关文章！