什么是Java二分查找非遞歸

本篇內(nèi)容主要講解“什么是Java二分查找非遞歸”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“什么是Java二分查找非遞歸”吧!

基本介紹

1.二分查找只適用于從有序的數(shù)列中進(jìn)行查找(比如數(shù)字和字母)，將數(shù)列排序后再進(jìn)行查找。

2.二分查找法的運(yùn)行時(shí)間為對(duì)數(shù)時(shí)間O(log2n),即查找到需要的目標(biāo)位置最多只需log2n步，假設(shè)從[0,99]的隊(duì)列中尋找目標(biāo)數(shù)30，則需要查找步數(shù)為log2(100)，即最多需要7次(2^6<100<2^7)。

代碼案例

package com.xie.algorithm;  public class BinarySearchNoRecur {     public static void main(String[] args) {         int[] arr = {1, 3, 8, 10, 11, 67, 100};         int index = binarySearch(arr, 1);         System.out.println("index = " + index);     }      /**      * 二分查找非遞歸實(shí)現(xiàn)      *      * @param arr    待查找的數(shù)組,arr是升序排列      * @param target 需要查找的數(shù)      * @return 返回對(duì)應(yīng)的下標(biāo) ，-1 表示沒(méi)有找到      */     public static int binarySearch(int[] arr, int target) {         int left = 0;         int right = arr.length - 1;         while (left <= right) {             int mid = (left + right) / 2;             if (arr[mid] == target) {                 return mid;             } else if (arr[mid] > target) {                 //需要向左邊查找                 right = mid - 1;              } else {                 //需要向右邊查找;                 left = mid + 1;             }         }         return -1;     } }

基本介紹

1.插值查找算法類似于二分查找，不同的是插值查找每次從自適應(yīng)的mid處開始查找。

2.二分查找中求mid索引的公式轉(zhuǎn)成插值查找mid索引公式，low表示左邊的索引，high表示右邊的索引，key表示要查找的值

代碼案例

package com.xie.search;  import java.util.ArrayList; import java.util.List;  public class InsertValueSearch {     static int count = 0;      public static void main(String[] args) {         int[] arr = new int[102];         arr[0] = 1;         arr[1] = 1;         for (int i = 2; i < 102; i++) {             arr[i] = i;         }         List<Integer> indexList = insertValueSearch(arr, 0, arr.length - 1, 1);         System.out.println("indexList = " + indexList);         System.out.println("查找次數(shù)：" + count);          /*         indexList = [1, 0]         查找次數(shù)：1          */     }      /**      * 插值查找，返回索引集合      *      * @param arr       數(shù)組      * @param left      左邊索引      * @param right     右邊索引      * @param findValue 要查找的值      * @return 找到就返回所有索引的集合，沒(méi)有就返回空      */     public static List<Integer> insertValueSearch(int[] arr, int left, int right, int findValue) {         count++;         List<Integer> indexList = new ArrayList<Integer>();         //注意：findValue < arr[0] || findValue > arr[arr.length - 1] 這個(gè)必須要，否則mid可能越界         if (left > right || findValue < arr[0] || findValue > arr[arr.length - 1]) {             return new ArrayList<Integer>();         }         int mid = left + (right - left) * (findValue - arr[left]) / (arr[right] - arr[left]);         int midValue = arr[mid];          if (findValue > midValue) {             return insertValueSearch(arr, mid + 1, right, findValue);         } else if (findValue < midValue) {             return insertValueSearch(arr, left, mid - 1, findValue);         } else {             //如果找到了，再向左掃描，將滿足條件的加入indexList             int temp = mid - 1;             while (true) {                 if (temp < 0 || arr[temp] != findValue) {                     break;                 }                 indexList.add(temp);                 temp--;             }              //再向右掃描,將滿足條件的加入indexList             temp = mid + 1;             while (true) {                 if (temp > right || arr[temp] != findValue) {                     break;                 }                 indexList.add(temp);                 temp++;             }             indexList.add(mid);             return indexList;         }     } }

注意事項(xiàng)

1. 對(duì)于數(shù)據(jù)量大，關(guān)鍵字分布比較均勻的查找表來(lái)說(shuō)，采用插值查找，速度較快。

2. 關(guān)鍵字分布不均勻的情況下，該方法不一定比二分法要好。

到此，相信大家對(duì)“什么是Java二分查找非遞歸”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！