首頁  >  文章  >  Java  >  Java演算法關於二分查找法的範例講解

Java演算法關於二分查找法的範例講解

黄舟
黄舟原創
2017-08-10 09:20:431202瀏覽

這篇文章主要介紹了java演算法之二分查找法的實例詳解的相關資料,這裡提供簡單實例幫助大家學習理解這部分內容,需要的朋友可以參考下

java演算法二分查找法的實例詳解

#原理

#假定查找範圍為有序數組(如昇序排列),要從中尋找某一元素,如果該元素在此數組中,則傳回其索引,否則傳回-1。透過數組長度可取出中間位置元素的索引,將其值與目標值比較,如果中間位置元素值大於目標值,則在左部分進行查找,如果中間位置值小於目標值,則在右部分進行查找,如此循環,直到結束。二分查找演算法之所以快是因為它沒有遍歷數組的每個元素,而僅僅是查找部分元素就能找到目標或確定其不存在,當然前提是查找範圍為有序數組。

Java的簡單實作


package me.geed.algorithms; 
 
public class BinarySearch { 
 
  /** 
   * 从一个有序数组(如升序)中找到值为key元素 
   * @param key 
   * @param array 
   * @return 如果找到目标元素,则返回其在数组中的索引,否则返回-1 
   */ 
  public static int find(int key, int[] array){ 
    int low = 0; 
    int high = array.length - 1; 
    while (low <= high) { 
      int mid = low + (high - low) / 2; 
      if (array[mid] > key) { 
        high = mid - 1; 
      } else if (array[mid] < key) { 
        low = mid + 1; 
      } else { 
        return mid; 
      }       
    } 
    return -1;    
  } 
   
  public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    int[] array = {2, 3, 5, 9, 10, 13, 23, 45, 78, 89, 100, 128, 256}; 
    System.out.println("目标元素索引值:" + BinarySearch.find(9, array));     
    System.out.println("目标元素索引值:" + BinarySearch.find(26, array)); 
  } 
 
}

輸出結果為:


目标元素索引值:3 
目标元素索引值:-1

二分查找演算法的時間複雜度

假設範圍數組長度為N,則二分查找的時間複雜度為O(logN)

以上是Java演算法關於二分查找法的範例講解的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn