這篇文章主要介紹了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中文網其他相關文章!