小白懂演算法之二分查找
- 2020 年 11 月 12 日
- 筆記
最近重頭刷各種演算法，發現自己遺忘了好多；趕緊刷了幾道來鞏固下記憶，也順便簡單做一個分享，希望能幫到一些小夥伴吧！
一.簡介
二分查找是一種查找元素效率特別高的查找演算法，也稱「折半演算法」。
二.前提
二分查找最重要的一個前提條件是 要查找的集合或者序列 必須是 有序的
三.查找的流程
二分查找的流程：
1）.確定一個查找值
2）.找出序列裡面中間的值
3）.比較查找值和中間值，兩種結果：
》相同，值找到了
》不相同，縮小1/2的的範圍，重複2）.3）的步驟
四.圖解（圖片來源百度）
五.程式碼實現
天上飛的理念，終歸得有地上的實現。不然就是在吹水了，語言的話使用Java來實現，這裡採用兩種方式：遞歸和while循環。
遞歸實現二分查找
/** * 使用遞歸實現二分查找 * @param sortedArr：查找的有序數組 * @param key：查找值，現在目前大多人都叫做關鍵字，用key表示 * @param low：起點 * @param high：終點 * @return */ public static boolean binarySearchByRecursion(int[] sortedArr, int key, int low, int high) { /** * 校驗： * 1.如果 key > sortedArr[high],該值肯定找不到 * 2.如果 key < sortedArr[low],該值肯定找不到 * 3.如果low > high，邏輯不成立，不存在中間值。 */ if(key < sortedArr[low] || key > sortedArr[high] || low > high) { return false; } /** * 得到中間值的下標，有兩種結果： * 1.奇數。java默認是向下取整的，取奇數作為中間索引沒毛病 * 2.偶數。可取偶數 或者 偶數+1 都行。這裡直接取偶數 */ int mid = (high+low)/2; //得到中間值的下標 /* * 判斷查找值和中間值 * 1. 查找值 > 中間值，起點向右縮小範圍，遞歸調用本方法 * 2.查找值 < 中間值，終點向左縮小範圍，遞歸調用本方法 * 3.查找值 = 中間值，值找到 */ if(key == sortedArr[mid]) { //查找值 = 中間值 return true; //返回true }else if(key > sortedArr[mid]) { //查找值 > 中間值 //起點縮小範圍 low = mid + 1; //遞歸調用本函數 return binarySearchByRecursion(sortedArr,key,low,high); }else if(key < sortedArr[mid]){ //查找值 < 中間值 //終點縮小範圍 high = mid - 1; //遞歸調用本函數 return binarySearchByRecursion(sortedArr,key,low,high); } return false; }
main方法測試：
public static void main(String[] args) { //準備一個有序數組 int[] sortedArr = new int[] {1,2,3,4,5,6,7,8,9,10,11,12,13,14}; //準備一個查找值 int key = 2; //準備起點位置和終點位置 int low = 0; int high = sortedArr.length-1; //調用二分查找方法返回一個布爾標識符，true - 代表找到，false代表找不到 boolean result = binarySearchByRecursion(sortedArr,key,low,high); //列印結果 if(result) { System.out.println("序列中存在"+key); }else { System.out.println("序列中不存在"+key); } }
while實現二分查找
public static boolean binarySearchByWhile(int[] sortedArr, int key, int low, int high) { /** * 校驗： * 1.如果 key > sortedArr[high],該值肯定找不到 * 2.如果 key < sortedArr[low],該值肯定找不到 * 3.如果low > high，邏輯不成立，不存在中間值。 */ if(key < sortedArr[low] || key > sortedArr[high] || low > high) { return false; } while(low<=high) { //滿足起點<=終點就可繼續，因為兩者間能產生中間值 //得到中間下標值 int mid = (high+low)/2; //若key = sortedArr[mid] if(key == sortedArr[mid]) { return true; }else if(key > sortedArr[mid]) { //若key > sortedArr[mid] //縮小起點範圍 low = mid + 1; }else if(key < sortedArr[mid]){ //若key < sortedArr[mid] //縮小終點範圍 high = mid -1; } } //找不到返回false return false; }
main方法測試：
public static void main(String[] args) { //創建有序數組 int[] sortedArr = new int[] {1,2,3,4,5,6,7,8,9,10}; //創建查找值 int key = 10; //創建起點和終點 int low = 0; int high = sortedArr.length-1; //調用二分查找方法，返回true代表找到，否則找不到 boolean result = binarySearchByWhile(sortedArr,key,low,high); //列印結果 if(result) { System.out.println("序列中存在"+key); }else { System.out.println("序列中不存在"+key); } }
如果上面有任何不妥的地方，歡迎大家在下面留言來糾正！
覺得不錯的話，動動小手點個推薦支援下作者唄！
