您好,登錄后才能下訂單哦!
什么是二分法查找:
二分法也就是折半查找,在有序的數(shù)列中查找指定的元素,設定最小索引(low)和最大索引(height-1)還有中間值mid((low+height-1)/2),這種查找,如果中間值比指定元素小讓low=mid+1,如果中間值比指定元素大,讓height=mid-1;
代碼實現(xiàn):
import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; import java.util.Scanner; public class Main2 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int arr[] = { 2, 5, 6, 8, 9, 4, 7 }; Arrays.sort(arr); int deix(索引) = getxiabiao(arr, 7); } public static int getxiabiao(int[] arr, int key) { int heigh = arr.length-1; int low = 0; int mid = 0; while (low <= heigh) { mid = low + (heigh - low)/2; if (arr[mid] == key) { return mid; } else if (arr[mid] < key) { low = mid + 1; } else if (arr[mid] > key) { heigh = mid - 1; } } return -1; } }
中間值的設定有兩種方法;
算法一: mid = (low + high) / 2
算法二: mid = low + (high – low)/2
乍看起來,算法一簡潔,算法二提取之后,跟算法一沒有什么區(qū)別。但是實際上,區(qū)別是存在的。
算法一的做法,在極端情況下,(low + high)存在著溢出的風險,進而得到錯誤的mid結(jié)果,導致程序錯誤,而算法二能夠保證計算出來的mid,一定大于low,小于high,不存在溢出的問題。
以上就是java實現(xiàn)二分法查找的詳細內(nèi)容,更多請關(guān)注億速云其它相關(guān)文章!
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。