关于二分法查找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;

   }


}

• 这是结果图

  
  
  程序结果图