美文网首页
输入一个数组,利用二分法查找

输入一个数组,利用二分法查找

作者: 小二上酒hua | 来源:发表于2017-09-11 16:55 被阅读0次

    关于二分法查找Java的实现

    对于一维数组的查找我们采用一个for循环遍历一次数组就可以实现,但有时候当数组太大,用二分法来实现
    可以节省更多的内存,当然二分法也只能实现有序序列的查找,这里我们就以一个递增的数组来说

    输入一个人数组,关于二分法的实现主要的就是设定一个中间值mid = (low + high)/2
    假设我们要查找的数为 m

    • 当mid=m急速表示我们找到了这个数,返回该数的位置;
    • 当mid<m时,因为数组时递增的,就表示我们所查找的数在mid的右边,我们就让low = mid+1;
    • 当mid>m时,因为数组时递增的,就表示我们所查找的数在mid的左边,我们就让right = mid-1;
    • 如果一直找不到就表示不存在,返回-1了。

    具体的Java代码如下:

    package com.dxh;
    
    import java.util.Scanner;
    
    public class DichotomySearch {
        static int num;
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            System.out.println("按要求输入:");
            int high = in.nextInt()+1;//输入数组的长度
            int low = in.nextInt();//输入开始查询的位置
            int findvalue = in.nextInt();//输入要查找的值
            int [] array = new int [high];//输入要查询的数组
            for(int i = 0;i<high;i++){
                array[i] = in.nextInt();
            }
            System.out.println("查询的数的位置在"+SearchResult(array, low, high-1, findvalue));
            System.out.println("查询轮数"+num);
            num = 0;
            System.out.println("查询的数的位置在"+SrearchResult1(array, findvalue));
            System.out.println("查询轮数"+num);
        }
        /*
         递归实现二分查找
         需要知道开始和结束的位置
          */
       public static int SearchResult(int [] array,int low ,int high,int findValue){
    
           if(array == null)return -1;
           num++;
          if(low<=high){
               int mid = (low + high)/2;
               if(array[mid] == findValue){
                   return mid;
               }else if(array[mid] < findValue){
                   return SearchResult( array, mid+1, high, findValue);
               }else{
                   return SearchResult(array, low, mid-1, findValue);
               }
           }else{
               return -1;
    
           }
       }
       /**
        * 循环来实现二分查找
        */
       public static int SrearchResult1(int [] array,int findvalue){
           if(array == null) {
               return -1;
           }
           int high = array.length-1;
           int low = 0;
           while(low<=high){
               num++;
               int mid = (low+high)/2;
               if(array[mid] == findvalue){
                   return mid;
               }else if(array[mid]<findvalue){
                   low = mid+1;
    
               }else{
                   high = mid-1;
               }
           }
           return -1;
    
       }
    
    
    }
    
    
    • 这是结果图


      程序结果图

    相关文章

      网友评论

          本文标题:输入一个数组,利用二分法查找

          本文链接:https://www.haomeiwen.com/subject/twyfsxtx.html