这篇文章主要讲解了“Java怎么实现二分法查找”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“Java怎么实现二分法查找”吧！
二分法查找
概述
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。
但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
归并排序即运用了二分法的思想。首先需要一个由小到大排序好的数组，先对比中间的值，如果比要找的大，则向前找，取中间值前面的一半再找中间值再对比。
如果比要找的小，则向后找，取中间值后面的一半再取中间值再对比。
递归实现
这里，我使用了递归的方法进行实现。
首先需要确认查找的范围，即有一个左索引和右索引，每次取(left+right)/2为中间值，比较要查找的元素和中间值的大小，若中间值大，则向前找，即递归范围为left ，mid-1。反之向右找，即递归范围mid+1，right。若相等即为找到。
但是需要继续向此索引的前后找找看有没有和其相等的值，一并加入到集合中，最后返回这个集合。
递归实现代码
package search;import java.util.ArrayList;import java.util.List;public class BinarySearch { public static void main(String[] args) { int[] array = {1,1,1,2,3,4,5,6,7}; List<Integer> integers = binarySearch(array, 0, array.length - 1, 1);// for (Integer integer : integers) {// System.out.print(integer+ " ");// } System.out.println(integers); } public static List<Integer> binarySearch(int[] array, int left, int right, int value){ //如果左索引大于右索引，则说明全部遍历完了，也没有找到相应的值，返回空集合即可 if (left>right){ return new ArrayList<Integer>(); } //获取中间值的下标（二分） int mid = (left+right)/2; //如果要找的值比中间值小，则继续向左找 if (value < array[mid]){ return binarySearch(array, left, mid-1, value); //要找的值比中间值小大，则向右找 }else if (value > array[mid]){ return binarySearch(array, mid+1, right, value); //否则，说明相等，找到了 }else { //找到一个，还需要向左右找找看有没有相同的值 List<Integer> resultList = new ArrayList(); //向左循环找，如果有，则加入到集合中 int temp = mid - 1; while (temp>=0 && array[temp] == value){ resultList.add(temp); temp -= 1; } //向右循环找，如果有，则加入到集合中 temp = mid + 1; while (temp < array.length && array[temp] == value){ resultList.add(temp); temp += 1; } //将一开始找到的那个索引页加入到集合中。 resultList.add(mid); return resultList; } } //以下这段代码来自百度百科，供大家参考。 public static int binarySearch(Integer[] srcArray, int des) { //定义初始最小、最大索引 int start = 0; int end = srcArray.length - 1; //确保不会出现重复查找，越界 while (start <= end) { //计算出中间索引值 int middle = (end + start)>>>1 ;//防止溢出 if (des == srcArray[middle]) { return middle; //判断下限 } else if (des < srcArray[middle]) { end = middle - 1; //判断上限 } else { start = middle + 1; } } //若没有，则返回-1 return -1; }}循环实现代码(非递归)
package search;import java.util.ArrayList;import java.util.Arrays;import java.util.List;public class BinarySearch3 { public static void main(String[] args) { int[] array = {1,1,1,1,1,2,3,4,5,6,7}; System.out.println(BinarySearch3.binarySearch(array, 7)); } public static List<Integer> binarySearch(int[] array, int key){ List<Integer> resultList = new ArrayList<>(); int start = 0; int end = array.length - 1; while (start <= end){ int mid = (start + end) / 2; int midValue = array[mid]; if (key > midValue){ //key比中间值大。向右找 start = mid + 1; } else if (key < midValue){ //key比中间值小。向左找 end = mid - 1; } else { //否则就找到了 //先向左找有没有相同值 int temp = mid -1; while (temp >= start && array[temp] == key){ resultList.add(temp); temp -= 1; } //将一开始找到的加入结果集 resultList.add(mid); //再向右找找有没有相同值 temp = mid + 1; while (temp <= end && array[temp] == key){ resultList.add(temp); temp += 1; } break; } } return resultList; }}二分法查找（递归、循环）
public class BinarySearch { //循环 private static int binarySearchByCycle(int[] arr,int num) { int start = 0; int end = arr.length - 1; while (start <= end){ int mid = (start + end) / 2; if(num == arr[mid]){ return mid; }else if(num > arr[mid]){ start = mid + 1; }else { end = mid - 1; } } return -1; } //递归 private static int binarySearchByRecursion(int[] arr,int num,int start,int end) { int mid = (start + end) / 2; if(num == arr[mid]){ return mid; }else if(num > arr[mid]){ start = mid + 1; }else { end = mid - 1; } if(start <= end){ mid = binarySearchByRecursion(arr,num,start,end); //递归继续寻找 }else { mid = -1; } return mid; }}感谢各位的阅读，以上就是“Java怎么实现二分法查找”的内容了，经过本文的学习后，相信大家对Java怎么实现二分法查找这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是编程网，小编将为大家推送更多相关知识点的文章，欢迎关注！
