Java怎么实现二分法查找

这篇文章主要讲解了“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怎么实现二分法查找这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是编程网，小编将为大家推送更多相关知识点的文章，欢迎关注！