溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹了Java二分查找算法實現代碼實例,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
二分查找:
兩種方式: 非遞歸方式和遞歸方式
主要思路: 對于已排序的數組(先假定是從小到大排序), 先定義兩個"指針", 一個"指向"首元素low, 一個"指向"末尾元素high. 然后, 開始折半比較, 即讓要查找的數與數組中間的元素(索引為 low+high/2)比較. 若要查找的數比中間數小, 說明要查找的數在數組左側(注意前提是數組從小到大排序), 否則說明該數在數組的右側. 如果low最后還比high大,倆"指針"交叉了, 說明沒有找到該數, 即數組不存在該數.
注意事項: 排序規則與數組的排序順序有關, 即從大到小排序和從小到大排序是不一樣的!!!
代碼如下
class BinarySearch {
// 二分查找非遞歸方式
// arr 給定已排序數組
// num 要查找的數
public static int search(int[] arr, int num) {
int low = 0;
int high = arr.length - 1;
int mid = 0;
while (low <= high) {
mid = (low + high) / 2;
if (num < arr[mid]) {
high = mid - 1;
}
if (num > arr[mid]) {
low = mid + 1;
}
if (num == arr[mid]) {
return mid;
}
}
return -1; // 沒找到
}
// 二分查找遞歸方式
// arr 給定已排序數組
// num 要查找的數
// low 初始左側指針 指向第一個元素
// high 初始末尾指針 指向最后一個元素
public static int binarySearch(int[] arr, int num, int low, int high) {
int mid = (low + high) / 2;
// 遞歸結束條件
if (low > high) {
return -1;
}
if (num < arr[mid]) {
return binarySearch(arr, num, low, mid - 1);
} else if (num == arr[mid]) {
return mid;
} else {
return binarySearch(arr, num, mid + 1, high);
}
}
public static void main(String[] args) {
// 給定數組 從小到大排序.
int[] arr = {2, 3, 5, 7, 8, 9, 11, 12, 15};
// int[] arr = {15, 12, 11, 9, 8, 7, 5, 3, 2};
int m = 3;
// int index = search(arr, m);
int index = binarySearch(arr, m, 0, arr.length - 1);
System.out.println(index);
}
}
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
