Comment implémenter la recherche binaire en Java

Recherche binaire

Vue d'ensemble

La recherche binaire est également appelée recherche binaire (Binary Search), qui est une méthode de recherche plus efficace.

Cependant, la recherche binaire nécessite que le tableau linéaire adopte une structure de stockage séquentielle et que les éléments du tableau doivent être classés dans l'ordre par mots-clés.

Le tri par fusion utilise l'idée de dichotomie. Tout d'abord, vous avez besoin d'un tableau trié de petit à grand. Comparez d'abord la valeur moyenne si elle est plus grande que ce que vous recherchez, prenez la première moitié de la valeur moyenne, puis trouvez la valeur moyenne avant de comparer.

S'il est plus petit que ce que vous recherchez, recherchez en arrière, prenez la moitié après la valeur moyenne, puis prenez la valeur moyenne et comparez.

Implémentation récursive

Ici, j'ai utilisé la méthode récursive pour implémenter.

Tout d'abord, vous devez confirmer la plage de recherche, c'est-à-dire qu'il y a un index gauche et un index droit À chaque fois, (gauche+droite)/2 est pris comme valeur médiane et la taille de l'élément. à rechercher et la valeur médiane sont comparées. Si la valeur médiane est grande, passez à Recherche avant, c'est-à-dire que la plage récursive est à gauche et au milieu de 1. Sinon, recherchez vers la droite, c'est-à-dire la plage récursive milieu+1, à droite. S'ils sont égaux, on le trouve.

Mais vous devez continuer à regarder avant et après cet index pour voir s'il y a une valeur égale, l'ajouter à l'ensemble, et enfin renvoyer cet ensemble.

Code d'implémentation récursive

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;
    }
}

Code d'implémentation de boucle (non récursive)

package search;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
 * @Author: sshdg
 * @Date: 2020/9/21 9:22
 */
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;
    }
}

Recherche binaire (récursive, boucle)

public class BinarySearch {
    /**
     * @author JadeXu
     * @// TODO: 2020/12/7 二分查找
     * 思路：
     * 1、获取数组的中间值，先获取下标，方便多次查找
     * 奇数位的数组直接获取中间位，偶数位的数组获取中间的第一位或第二位都可，一般获取第一位（因为与奇数位获取中间值的方法一样）
     * 2、获取查找的区间范围，start：区间开始的下标，end：区间结束的下标
     * 3、判断查找的数和中间位的数是否相同
     * 相同时，直接返回需要的数据，跳出方法
     * 大于时，即数可能在中间值右边的区间内，此时start = mid+1，即mid往后移一位，就得到了中间值右边区间的开始下标
     * 小于时，即数可能在中间值左边的区间内，此时end = mid-1，即mid往前移一位，就得到了中间值左边区间的结束下标
     * 当一个区间里，开始下标小于等于结束下标时，该区间才是有效区间，才能继续查找。否则无效，返回找不到，跳出方法
     */
    //循环
    /**
     * @param arr 已经升序好的int[]
     * @param num 需要查找的数字
     * @return 找到则返回下标，没找到则返回-1
     */
    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;
    }
    //递归
    /**
     * @param arr 已经升序好的int[]
     * @param num 需要查找的数字
     * @param start 区间开始下标
     * @param end 区间结束下标
     * @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;
    }
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!