JAVA 二分搜索法

  在一组数组中查找一个数很多人看到这个问题后的最初想法估计都是直接从前面和后面按顺序查找，但是直接查找的复杂度是 O(N)，并不是一个好的方案。我们还是要从二分查找法入手。

导入模块

import java.util.Arrays;
import java.util.Scanner;

实现输入数组

public int[] inputArray(){//输入数组
        System.out.println("请输入数组长度：");
        Scanner in=new Scanner(System.in);
        int[] array=new int[in.nextInt()];
        for (int i = 0; i < array.length; i++) {//输入数组
            System.out.println("请输入第"+(i+1)+"个数：");
            array[i]=in.nextInt();
        }
        System.out.println("您输入的数组为"+Arrays.toString(array));
        return array;
    }

查找

public void findOut(int[] array,int num){//查找
        int high = array.length-1;
        int low = 0;
        for(int count=0; countarray[middle]){
                low=middle;
            }else {
                System.out.println(num+"找到了，它是这组数组中第"+(middle+1)+"个数");
                break;}

        }
    }

完整代码

package Fan.Da.wei;


import java.util.Arrays;
import java.util.Scanner;


public class BinarySearch {
    public int[] inputArray(){//输入数组
        System.out.println("请输入数组长度：");
        Scanner in=new Scanner(System.in);
        int[] array=new int[in.nextInt()];
        for (int i = 0; i < array.length; i++) {//输入数组
            System.out.println("请输入第"+(i+1)+"个数：");
            array[i]=in.nextInt();
        }
        System.out.println("您输入的数组为"+Arrays.toString(array));
        return array;
    }

    public void findOut(int[] array,int num){//查找
        int high = array.length-1;
        int low = 0;
        for(int count=0; countarray[middle]){
                low=middle;
            }else {
                System.out.println(num+"找到了，它是这组数组中第"+(middle+1)+"个数");
                break;}

        }
    }

    public static void main(String[] args){
        BinarySearch binarySearch = new BinarySearch();
        int[] array = binarySearch.inputArray();
        System.out.println("正在排序中···");
        Arrays.sort(array);//实现数组排序
        System.out.println("排序后的数组为"+Arrays.toString(array));
        System.out.println("请输入你要查找的数：");
        Scanner scanner=new Scanner(System.in);
        int num=scanner.nextInt();
        binarySearch.findOut(array,num);
//        System.out.println("请输入数组长度：");
//        Scanner in=new Scanner(System.in);
//        int[] array=new int[in.nextInt()];
//        for (int i = 0; i < array.length; i++) {//输入数组
//            System.out.println("请输入第"+(i+1)+"个数：");
//            array[i]=in.nextInt();
//        }
//        System.out.println("您输入的数组为"+Arrays.toString(array));
//        System.out.println("正在排序中···");
//        for (int n = 0; n < array.length; n++) {//实现输入数组从小到大排序
//            for (int m = 0 ; m < array.length-n-1; m++) {
//                if(array[m]>array[m+1]){
//                    int temp = array[m];
//                    array[m]=array[m+1];
//                    array[m+1]=temp;
//                }
//            }
//        }

//        Arrays.sort(array);//排序数组
//        System.out.println("排序后的数组为"+Arrays.toString(array));
//        System.out.println("请输入你要查找的数：");
//        Scanner scanner=new Scanner(System.in);
//        int num=scanner.nextInt();
//        int high = array.length-1;
//        int low = 0;
//        for(int count=0; count
//            int middle=(low+high)/2;
//            if(array.length-1==count){
//                System.out.println("没有找到！");
//            } else if(num
//                high=middle;
//            } else if(num>array[middle]){
//                low=middle;
//            }else {
//                System.out.println(num+"找到了，它是这组数组中第"+(middle+1)+"个数");
//                break;}
//
//        }
    }
}

运行结果