Java 二分查找的實現(xiàn)及圖例解析

更新時間：2020年12月07日 14:19:42 作者：長河落日圓

這篇文章主要介紹了Java 二分查找的實現(xiàn)，幫助大家更好的理解和使用Java，感興趣的朋友可以了解下

二分查找又稱折半查找，它是一種效率較高的查找方法。

折半查找的算法思想是將數列按有序化(遞增或遞減)排列，查找過程中采用跳躍式方式查找，即先以有序數列的中點位置為比較對象，如果要找的元素值小于該中點元素，則將待查序列縮小為左半部分，否則為右半部分。通過一次比較，將查找區(qū)間縮小一半。折半查找是一種高效的查找方法。它可以明顯減少比較次數，提高查找效率。但是，折半查找的先決條件是查找表中的數據元素必須有序。

折半查找法的優(yōu)點是比較次數少，查找速度快，平均性能好;其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經常變動而查找頻繁的有序列表。

二分算法步驟描述：

1.確定整個查找區(qū)間的中間位置 mid = （ left + right ）/ 2

2.用待查關鍵字值與中間位置的關鍵字值進行比較；

若相等，則查找成功

若大于，則在后（右）半個區(qū)域繼續(xù)進行折半查找

若小于，則在前（左）半個區(qū)域繼續(xù)進行折半查找

3.對確定的縮小區(qū)域再按折半公式，重復上述步驟。

4.得到結果：要么查找成功，要么查找失敗。折半查找的存儲結構采用一維數組存放。折半查找算法舉例

注意：查找失?。丛诓檎覂热葜袥]有你要找的），這時控制臺并不會報錯。

代碼實例：

package com.shuzu;

public class Demo7 {

  public static void main(String[] args) {
    // TODO Auto-generated method stub
    // 測試，數組(有序，以升序序列為例。這里是園友留言，提示糾正的。)
    int arr[] = { 1, 3, 4, 7, 11, 16, 33, 43, 65, 77, 88, 90, 99, 110 };

    BinaryFind bf = new BinaryFind();
    bf.find(0, arr.length - 1, 33, arr);
  }
}

// 定義一個二分查找的類
class BinaryFind {
  public void find(int leftIndex, int rightIndex, int val, int arr[]) {
    // 首先找到中間的數，這里不用擔心。/代表取整。    //（之前的錯誤，被園友糾正：Java中，除不盡會自動取整）
    int midIndex = (rightIndex + leftIndex) / 2;
    int midVal = arr[midIndex];

    if (rightIndex >= leftIndex) {
      // 如果要找的數比midVal大
      if (midVal > val) {
        // 在arr數組的左邊找
        find(leftIndex, midIndex - 1, val, arr);
      } else if (midVal < val) {
        // 在arr數組的右邊找
        find(midIndex + 1, rightIndex, val, arr);
      } else if (midVal ==val) {
        System.out.println("找到下標" + midIndex);
      }
    }
  }
}