關(guān)于二分法查找Java的實現(xiàn)

對于一維數(shù)組的查找我們采用一個for循環(huán)遍歷一次數(shù)組就可以實現(xiàn)，但有時候當數(shù)組太大，用二分法來實現(xiàn)
可以節(jié)省更多的內(nèi)存，當然二分法也只能實現(xiàn)有序序列的查找，這里我們就以一個遞增的數(shù)組來說

輸入一個人數(shù)組，關(guān)于二分法的實現(xiàn)主要的就是設定一個中間值mid = （low + high）/2
假設我們要查找的數(shù)為 m

• 當mid=m急速表示我們找到了這個數(shù)，返回該數(shù)的位置；
• 當mid<m時，因為數(shù)組時遞增的，就表示我們所查找的數(shù)在mid的右邊，我們就讓low = mid+1；
• 當mid>m時，因為數(shù)組時遞增的，就表示我們所查找的數(shù)在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;//輸入數(shù)組的長度
        int low = in.nextInt();//輸入開始查詢的位置
        int findvalue = in.nextInt();//輸入要查找的值
        int [] array = new int [high];//輸入要查詢的數(shù)組
        for(int i = 0;i<high;i++){
            array[i] = in.nextInt();
        }
        System.out.println("查詢的數(shù)的位置在"+SearchResult(array, low, high-1, findvalue));
        System.out.println("查詢輪數(shù)"+num);
        num = 0;
        System.out.println("查詢的數(shù)的位置在"+SrearchResult1(array, findvalue));
        System.out.println("查詢輪數(shù)"+num);
    }
    /*
     遞歸實現(xiàn)二分查找
     需要知道開始和結(jié)束的位置
      */
   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;

       }
   }
   /**
    * 循環(huán)來實現(xiàn)二分查找
    */
   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;

   }


}

• 這是結(jié)果圖

  
  
  程序結(jié)果圖