Java中的二分查找是什么意思

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

需求

對于一個有序的數(shù)組進(jìn)行二分查找{1,8,10,89,1000,1234}，輸入一個數(shù)看看該數(shù)組是否存在此數(shù)，并求出下標(biāo)，如果沒有就提示”沒有這個數(shù)據(jù)”。

思路分析

1. 鴻蒙官方戰(zhàn)略合作共建——HarmonyOS技術(shù)社區(qū)

2. 首先確定該數(shù)組中間的下標(biāo) mid=(left+right)/2.

3. 然后讓需要查找的數(shù)findValue和arr[mid]比較，findValue >  arr[mid]，說明要查找的數(shù)在arr[mid]的右邊，因此向右遞歸.findValue <  arr[mid]，說明要查找的數(shù)在arr[mid]的左邊，因此向左遞歸.findValue == arr[mid]，說明找打，就返回。

4. 退出遞歸的條件找到就結(jié)束遞歸。遞歸完整個數(shù)組仍然沒有找到findValue，需要結(jié)束遞歸，即當(dāng) left > right

代碼案例

package com.xie.search;  import java.util.ArrayList; import java.util.Arrays; import java.util.List;  public class BinarySearch {     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 = binarySearch(arr, 0, arr.length - 1, 1);         System.out.println("indexList = " + indexList);         System.out.println("查找次數(shù)：" + count);         /*         indexList = [1, 0]         查找次數(shù)：6          */     }      /**      * 二分查找,查找符合值得所有索引集合      *      * @param arr       數(shù)組      * @param left      左邊索引      * @param right     右邊索引      * @param findValue 查找的值      * @return 找到就返回所有索引的集合，沒有就返回空      */     public static List<Integer> binarySearch(int[] arr, int left, int right, int findValue) {         count++;         List<Integer> indexList = new ArrayList<Integer>();         //當(dāng)left > right時，說明遞歸完畢         if (left > right) {             return new ArrayList<Integer>();         }         int mid = (left + right) / 2;         int midVal = arr[mid];         if (findValue > midVal) {             //查找的值比中間值大，向右遞歸             return binarySearch(arr, mid + 1, right, findValue);         } else if (findValue < midVal) {             //查找的值比中間值小，向左遞歸             return binarySearch(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;         }     } }

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