JavaSE基础50题:27(数组练习)二分查找

2023-12-29 06:09:41

概述

给定一个有序整数数组,实现二分查找。
二分查找的前提:必须是有序的数组!!

方法具体实现

如找数字5,定义L、R、M,其中M是L和R的中间位置,即(L+R) / 2 的位置。
如下图所示:
① L为0,R为4,此时M为2,2位置上的数字是3,3<5;
② 因为 3<5,所以,L=M+1的位置,R不变,此时M为 int (3+4)/2 = 3,3位置的数字为4,4<5;
③因为 4<5,所以,L=M+1的位置,R不变,此时M为4,4位置上的数字为5,故找到数字5.
在这里插入图片描述

代码

public class P27 {
    public static int func(int[] array,int num) {
        int left = 0;
        int rigth = array.length - 1;
        while (left <= rigth){ 
        //当left<=rigth时,进入循环,否则输出-1;
        //即你想要找的数组找到最后没找到,说明这个数组中没有你要找的数字,输出-1作提示。
            int mid = (left + rigth) / 2;
            if (num > array[mid]){
                left = mid + 1;
            }else if (num < array[mid]) {
                rigth = mid - 1;

            }else {
                return mid;
            }
        }
        return -1;
        }

    public static void main(String[] args) {
        int[] array = {11,22,33,44,55,66,77,88,99};
        int a = func(array,99);
        int b = func(array,2);
        
        System.out.println(a);
        System.out.println(b);
    }
}

//输出结果
8
-1

如果数组是无序的,就需要用Arrays.sort()方法先排个序,最终输出的位置是排完序后的位置。

    public static void main(String[] args) {
       int[] array2 = {2,5,6,3,8,4,1};
        Arrays.sort(array2); //此时的顺序为{1,2,3,4,5,6,8}
        System.out.println(func(array2, 1));
        System.out.println(func(array2,5));
    }

//输出结果
0
4

文章来源:https://blog.csdn.net/T2283380276/article/details/135279239
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。