如何使用二分法查找

本篇內(nèi)容介紹了“如何使用二分法查找”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠?qū)W有所成！

 1、二分法查找的背景

當數(shù)組或者集合中存放的元素數(shù)量非常多的時候，想要跟蹤具體某個元素的位置或者是否存在，常規(guī)方式是循環(huán)每一個元素直到找到要查找的元素為止。這樣的查找方式效率非常低下，這個時候需要使用二分法來實現(xiàn)，提高查找效率。

2、二分法查找的介紹

二分法查找(折半查找)，找指定數(shù)值所在的位置

百度百科是這樣介紹二分法查找的：

3、二分法查找的算法思想

假設(shè)數(shù)組是按升序排序的，對于給定的目標值aim，從數(shù)組的中間位置開始查找：1.若查找數(shù)據(jù)與中間元素值正好相等，則返回中間元素值的索引;2.若查找數(shù)值比中間值小，則以整個查找范圍的前半部分作為新的查找范圍;3.若查找數(shù)值比中間值大，則以整個查找范圍的后半部分作為新的查找范圍;注：查找成功返回索引，失敗返回-1

4、代碼實現(xiàn)

4.1 利用循環(huán)的方式實現(xiàn)二分法查找

public class BinarySearch {     public static void main(String[] args) {         // 生成一個隨機數(shù)組         int[] array = suiji();         // 對隨機數(shù)組排序         Arrays.sort(array);         System.out.println("產(chǎn)生的隨機數(shù)組為： " + Arrays.toString(array));          System.out.println("要進行查找的值： ");         Scanner input = new Scanner(System.in);         // 進行查找的目標值         int aim = input.nextInt();          // 使用二分法查找         int index = binarySearch(array, aim);         System.out.println("查找的值的索引位置： " + index);      }      /**      * 生成一個隨機數(shù)組      *       * @return 返回值，返回一個隨機數(shù)組      */     private static int[] suiji() {         // random.nextInt(n)+m  返回m到m+n-1之間的隨機數(shù)         int n = new Random().nextInt(6) + 5;         int[] array = new int[n];         // 循環(huán)遍歷為數(shù)組賦值         for (int i = 0; i < array.length; i++) {             array[i] = new Random().nextInt(100);         }         return array;     }      /**      * 二分法查找  ---循環(huán)的方式實現(xiàn)      *       * @param array 要查找的數(shù)組      * @param aim 要查找的值      * @return 返回值，成功返回索引，失敗返回-1      */     private static int binarySearch(int[] array, int aim) {         // 數(shù)組最小索引值         int left = 0;         // 數(shù)組最大索引值         int right = array.length - 1;         int mid;         while (left <= right) {             mid = (left + right) / 2;             // 若查找數(shù)值比中間值小，則以整個查找范圍的前半部分作為新的查找范圍             if (aim < array[mid]) {                 right = mid - 1;                 // 若查找數(shù)值比中間值大，則以整個查找范圍的后半部分作為新的查找范圍             } else if (aim > array[mid]) {                 left = mid + 1;                 // 若查找數(shù)據(jù)與中間元素值正好相等，則放回中間元素值的索引             } else {                 return mid;             }         }         return -1;     } }

代碼執(zhí)行結(jié)果：

產(chǎn)生的隨機數(shù)組為： [16, 33, 40, 46, 57, 63, 65, 71, 85] 要進行查找的值：  46 查找的值的索引位置： 3

若輸入的值找不到，則返回-1

產(chǎn)生的隨機數(shù)組為： [28, 41, 47, 56, 70, 81, 85, 88, 95] 要進行查找的值：  66 查找的值的索引位置： -1

4.2 利用遞歸的方式實現(xiàn)二分法查找

public class BinarySearch3 {     public static void main(String[] args) {         // 生成一個隨機數(shù)組         int[] array = suiji();         // 對隨機數(shù)組排序         Arrays.sort(array);         System.out.println("產(chǎn)生的隨機數(shù)組為： " + Arrays.toString(array));          System.out.println("要進行查找的值： ");         Scanner input = new Scanner(System.in);         // 進行查找的目標值         int aim = input.nextInt();          // 使用二分法查找         int index = binarySearch(array, aim, 0, array.length - 1);         System.out.println("查找的值的索引位置： " + index);     }      /**      * 生成一個隨機數(shù)組      *      * @return 返回值，返回一個隨機數(shù)組      */     private static int[] suiji() {         // Random.nextInt(n)+m  返回m到m+n-1之間的隨機數(shù)         int n = new Random().nextInt(6) + 5;         int[] array = new int[n];         // 循環(huán)遍歷為數(shù)組賦值         for (int i = 0; i < array.length; i++) {             array[i] = new Random().nextInt(100);         }         return array;     }      /**      * 二分法查找 ---遞歸的方式      *      * @param array 要查找的數(shù)組      * @param aim   要查找的值      * @param left  左邊最小值      * @param right 右邊最大值      * @return 返回值，成功返回索引，失敗返回-1      */     private static int binarySearch(int[] array, int aim, int left, int right) {         if (aim < array[left] || aim > array[right]) {             return -1;         }         // 找中間值         int mid = (left + right) / 2;         if (array[mid] == aim) {             return mid;         } else if (array[mid] > aim) {             //如果中間值大于要找的值則從左邊一半繼續(xù)遞歸             return binarySearch(array, aim, left, mid - 1);         } else {             //如果中間值小于要找的值則從右邊一半繼續(xù)遞歸             return binarySearch(array, aim, mid + 1, array.length-1);         }     } }

遞歸相較于循環(huán)，代碼比較簡潔，但是時間和空間消耗比較大，效率低。在實際的學習與工作中，根據(jù)情況選擇使用。

“如何使用二分法查找”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！