欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分法查找

程序员文章站 2022-04-30 22:49:14
...

二分法查找适用查找一组有序数列,例如10,15,25,36,49,55,62,78,99,200这种单调递增的数列

二分查找的基本思想如下:

       1、left对应数列第一个数的位置(即0),right对应数列最后一个数的位置(即n-1),mid设置为(left+right)/2。

       2、比较需要查找的数值key和mid这个位置所对应的数值大小,

                             若key小于arry[mid],则right=mid-1,查找区间变为[left,mid-1]

                             若key大于arry[mid],则left=mid+1,查找区间变为[mid+1,right]

                             若key等于arry[mid],则查找成功

       3、重复上述循环,直至查找成功或left>right

下面给出一张查找的例图,以数组10,15,25,36,49,55,62,78,99,200为例,查找78

二分法查找

     查找14

二分法查找

下面贴出代码

public static void main(String args[]){
        int[] arr ={10,20,30,40,50,60,70,80,90,100};
        int num_input;
        int mid = 0;
        int left=0;
        int right;
        System.out.println("请输入要查找的数");
        Scanner sc =new Scanner(System.in) ;
        num_input=sc.nextInt();
        
        right=arr.length-1;
        while(left<=right) {
            mid=(left+right)/2;
            if (num_input == arr[mid]) {
                break;
            }
            else if (num_input > arr[mid]){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        if(left>right){
            System.out.println("未找到");
        }else {
            System.out.println("找到数字"+arr[mid]);
        }
    }

做几次实验

二分法查找

二分法查找

 

 

相关标签: 算法