這篇文章主要介紹“如何使用Java二分查找”，在日常操作中，相信很多人在如何使用Java二分查找問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”如何使用Java二分查找”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！
基本思想：又叫折半查找，要求待查找的序列有序，是一種快速查找算法，時間復雜度為 O(logn)，要求數據集為一個有序數據集。
應用場景：一般用于查找數組元素，并且數組在查找之前必須已經排好序(一般是升序)。
步驟：
1、取中間位置的值與待查關鍵字比較，如果中間位置的值比待查關鍵字大，則在前半部分循環這個查找的過程，
2、如果中間位置的值比待查關鍵字小，則在后半部分循環這個查找的過程。
3、直到查找到了為止，否則序列中沒有待查的關鍵字。
代碼示例：
public static int biSearch(int []array,int a){ int lo=0; int hi=array.length-1; int mid; while(lo<=hi){ mid=(lo+hi)/2;//中間位置 if(array[mid]==a){ return mid+1; }else if(array[mid]<a){ //向右查找 lo=mid+1; }else{ //向左查找 hi=mid-1; } } return -1; }基本思想：比較前后相鄰的兩個數據，如果前面數據大于后面的數據，就將這二個數據交換。這樣對數組的第 0 個數據到 N-1 個數據進行一次遍歷后，最大的一個數據就“沉”到數組第 N-1 個位置。N=N-1，如果 N 不為 0 就重復前面二步，否則排序完成。
應用場景：數據量不大，對穩定性有要求，且數據基本有序的情況。
步驟：
1、將序列中所有元素兩兩比較，將最大的放在最后面。
2、將剩余序列中所有元素兩兩比較，將最大的放在最后面。
3、重復第二步，直到只剩下一個數。
代碼示例：
public static void bubbleSort1(int [] a, int n){ int i, j; for(i=0; i<n; i++){//表示 n 次排序過程。 for(j=1; j<n-i; j++){ if(a[j-1] > a[j]){//前面的數字大于后面的數字就交換 //交換 a[j-1]和 a[j] int temp; temp = a[j-1]; a[j-1] = a[j]; a[j]=temp; } } } }基本思想：通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應的位置并插入。
應用場景：數據量不大，對算法的穩定性有要求，且數據局部或者整體有序的情況。
步驟：
1、將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最后一個元素當成是未排序序列。
2、從頭到尾依次掃描未排序序列，將掃描到的每個元素插入有序序列的適當位置。(如果待插入的元素與有序序列中的某個元素相等，則將待插入元素插入到相等元素的后面。)
代碼示例：
public class InsertSort implements IArraySort { @Override public int[] sort(int[] sourceArray) throws Exception { // 對 arr 進行拷貝，不改變參數內容 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); // 從下標為1的元素開始選擇合適的位置插入，因為下標為0的只有一個元素，默認是有序的 for (int i = 1; i < arr.length; i++) { // 記錄要插入的數據 int tmp = arr[i]; // 從已經排序的序列最右邊的開始比較，找到比其小的數 int j = i; while (j > 0 && tmp < arr[j - 1]) { arr[j] = arr[j - 1]; j--; } // 存在比其小的數，插入 if (j != i) { arr[j] = tmp; } } return arr; } } 快速排序算法基本思想：選擇一個關鍵值作為基準值。比基準值小的都在左邊序列(一般是無序的)，比基準值大的都在右邊(一般是無序的)。一般選擇序列的第一個元素。
應用場景：數值范圍較大，相同值的概率較小，數據量大且不考慮穩定性的情況，數值遠大于數據量時威力更大。
步驟：
1、一次循環，從后往前比較，用基準值和最后一個值比較，如果比基準值小的交換位置，如果沒有繼續比較下一個，直到找到第一個比基準值小的值才交換。
2、找到這個值之后，又從前往后開始比較，如果有比基準值大的，交換位置，如果沒有繼續比較下一個，直到找到第一個比基準值大的值才交換。
3、直到從前往后的比較索引 > 從后往前比較的索引，結束第一次循環，此時，對于基準值來說，左右兩邊就是有序的了。
代碼示例：
public void sort(int[] a,int low,int high){ int start = low; int end = high; int key = a[low]; while(end>start){ //從后往前比較 while(end>start&&a[end]>=key) //如果沒有比關鍵值小的，比較下一個，直到有比關鍵值小的交換位置，然后又從前往后比較 end--; if(a[end]<=key){ int temp = a[end]; a[end] = a[start]; a[start] = temp; } //從前往后比較 while(end>start&&a[start]<=key) //如果沒有比關鍵值大的，比較下一個，直到有比關鍵值大的交換位置 start++; if(a[start]>=key){ int temp = a[start]; a[start] = a[end]; a[end] = temp; } //此時第一次循環比較結束，關鍵值的位置已經確定了。左邊的值都比關鍵值小，右邊的值都比關鍵值大，但是兩邊的順序還有可能是不一樣的，進行下面的遞歸調用 } //遞歸 if(start>low) sort(a,low,start-1);//左邊序列。第一個索引位置到關鍵值索引-1 if(end<high) sort(a,end+1,high);//右邊序列。從關鍵值索引+1 到最后一個 } }基本思想：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。
應用場景：數據量較大，不要求穩定性的情況。
步驟：
1、選擇一個增量序列 t1，t2，…，tk，其中 ti>tj，tk=1;
2、按增量序列個數 k，對序列進行 k 趟排序;
3、每趟排序，根據對應的增量 ti，將待排序列分割成若干長度為 m 的子序列，分別對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。
代碼示例：
private void shellSort(int[] a) { int dk = a.length/2; while( dk >= 1 ){ ShellInsertSort(a, dk); dk = dk/2; } } private void ShellInsertSort(int[] a, int dk) { //類似插入排序，只是插入排序增量是 1，這里增量是 dk,把 1 換成 dk 就可以了 for(int i=dk;i<a.length;i++){ if(a[i]<a[i-dk]){ int j; int x=a[i];//x 為待插入元素 a[i]=a[i-dk]; for(j=i-dk; j>=0 && x<a[j];j=j-dk){ //通過循環，逐個后移一位找到要插入的位置。 a[j+dk]=a[j]; } a[j+dk]=x;//插入 } } } 歸并排序算法基本思想：歸并(Merge)排序法是將兩個(或兩個以上)有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。
應用場景：內存少的時候使用，可以進行并行計算的時候使用。
步驟：
1、選擇相鄰兩個數組成一個有序序列。
2、選擇相鄰的兩個有序序列組成一個有序序列。
3、重復第二步，直到全部組成一個有序序列。
代碼示例：
public class MergeSortTest { public static void main(String[] args) { int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 }; print(data); mergeSort(data); System.out.println("排序后的數組："); print(data); } public static void mergeSort(int[] data) { sort(data, 0, data.length - 1); } public static void sort(int[] data, int left, int right) { if (left >= right) return; // 找出中間索引 int center = (left + right) / 2; // 對左邊數組進行遞歸 sort(data, left, center); // 對右邊數組進行遞歸 sort(data, center + 1, right); // 合并 merge(data, left, center, right); print(data); } /** * 將兩個數組進行歸并，歸并前面 2 個數組已有序，歸并后依然有序 * @param data * 數組對象 * @param left * 左數組的第一個元素的索引 * @param center * 左數組的最后一個元素的索引，center+1 是右數組第一個元素的索引 * @param right * 右數組最后一個元素的索引 */ public static void merge(int[] data, int left, int center, int right) { // 臨時數組 int[] tmpArr = new int[data.length]; // 右數組第一個元素索引 int mid = center + 1; // third 記錄臨時數組的索引 int third = left; // 緩存左數組第一個元素的索引 int tmp = left; while (left <= center && mid <= right) { // 從兩個數組中取出最小的放入臨時數組 if (data[left] <= data[mid]) { tmpArr[third++] = data[left++]; } else { tmpArr[third++] = data[mid++]; } } // 剩余部分依次放入臨時數組（實際上兩個 while 只會執行其中一個） while (mid <= right) { tmpArr[third++] = data[mid++]; } while (left <= center) { tmpArr[third++] = data[left++]; } // 將臨時數組中的內容拷貝回原數組中 // （原 left-right 范圍的內容被復制回原數組） while (tmp <= right) { data[tmp] = tmpArr[tmp++]; } } public static void print(int[] data) { for (int i = 0; i < data.length; i++) { System.out.print(data[i] + "\t"); } System.out.println(); } }基本思想： 把數組 arr 劃分為 n 個大小相同子區間(桶)，每個子區間各自排序，最后合并 。計數排序是桶排序的一種特殊情況，可以把計數排序當成每個桶里只有一個元素的情況。
應用場景：在數據量非常大，而空間相對充裕的時候是很實用的，可以大大降低算法的運算數量級。
步驟：
1、找出待排序數組中的最大值 max、最小值 min
2、我們使用動態數組 ArrayList 作為桶，桶里放的元素也用 ArrayList 存儲。桶的數量為(maxmin)/arr.length+1
3、遍歷數組 arr，計算每個元素 arr[i] 放的桶
4、每個桶各自排序
代碼示例：
public static void bucketSort(int[] arr){ int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for(int i = 0; i < arr.length; i++){ max = Math.max(max, arr[i]); min = Math.min(min, arr[i]); } //創建桶 int bucketNum = (max - min) / arr.length + 1; ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum); for(int i = 0; i < bucketNum; i++){ bucketArr.add(new ArrayList<Integer>()); } //將每個元素放入桶 for(int i = 0; i < arr.length; i++){ int num = (arr[i] - min) / (arr.length); bucketArr.get(num).add(arr[i]); } //對每個桶進行排序 for(int i = 0; i < bucketArr.size(); i++){ Collections.sort(bucketArr.get(i)); } }基本思想：將所有待比較數值(正整數)統一為同樣的數位長度，數位較短的數前面補零。然后，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以后,數列就變成一個有序序列。
應用場景：用于大量數，很長的數進行排序時的情況。
步驟：
1、將所有的數的個位數取出，按照個位數進行排序，構成一個序列。
2、將新構成的所有的數的十位數取出，按照十位數進行排序，構成一個序列。
代碼示例：
public class radixSort { inta[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,101,56,17,18,23,34,15,35,25,53,51}; public radixSort(){ sort(a); for(inti=0;i<a.length;i++){ System.out.println(a[i]); } } public void sort(int[] array){ //首先確定排序的趟數; int max=array[0]; for(inti=1;i<array.length;i++){ if(array[i]>max){ max=array[i]; } } int time=0; //判斷位數; while(max>0){ max/=10; time++; } //建立 10 個隊列; List<ArrayList> queue=newArrayList<ArrayList>(); for(int i=0;i<10;i++){ ArrayList<Integer>queue1=new ArrayList<Integer>(); queue.add(queue1); } //進行 time 次分配和收集; for(int i=0;i<time;i++){ //分配數組元素; for(intj=0;j<array.length;j++){ //得到數字的第 time+1 位數; int x=array[j]%(int)Math.pow(10,i+1)/(int)Math.pow(10, i); ArrayList<Integer>queue2=queue.get(x); queue2.add(array[j]); queue.set(x, queue2); } int count=0;//元素計數器; //收集隊列元素; for(int k=0;k<10;k++){ while(queue.get(k).size()>0){ ArrayList<Integer>queue3=queue.get(k); array[count]=queue3.get(0); queue3.remove(0); count++; } } } } }基本思想：在搜索算法中優化中，剪枝，就是通過某種判斷，避免一些不必要的遍歷過程，形象的說，就是剪去了搜索樹中的某些“枝條”，故稱剪枝。應用剪枝優化的核心問題是設計剪枝判斷方法，即確定哪些枝條應當舍棄，哪些枝條應當保留的方法。
應用場景：通常應用在 DFS 和 BFS 搜索算法中，尋找過濾條件，提前減少不必要的搜索路徑。
步驟：
1、基于訓練數據集生成決策樹，生成的決策樹要盡量大;
2、用驗證數據集最已生成的樹進行剪枝并選擇最優子樹，這時用損失函數最小作為剪枝的標準
代碼示例：
class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { Arrays.sort(candidates); LinkedList<Integer> track = new LinkedList<>(); combinationSum(candidates, 0, target, track); return result; } private List<List<Integer>> result = new ArrayList<>(); private void combinationSum(int[] candidates, int start, int target, LinkedList<Integer> track) { if (target < 0) { return; } else if (target == 0) { result.add(new LinkedList<>(track)); return; } for (int i = start; i < candidates.length; i++) { if (target < candidates[i]) { break; } track.add(candidates[i]); combinationSum(candidates, i, target - candidates[i], track); track.removeLast(); } } }基本思想：回溯算法實際上一個類似枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當發現已不滿足求解條件時，就“回溯”返回，嘗試別的路徑。
應用場景：設置一個遞歸函數，函數的參數會攜帶一些當前的可能解的信息，根據這些參數得出可能解或者不可能而回溯，平時經常見的有 N 皇后、數獨、集合等情況。
步驟：
1、定義一個解空間，它包含問題的解;
2、利用適于搜索的方法組織解空間;
3、利用深度優先法搜索解空間;
4、利用限界函數避免移動到不可能產生解的子空間。
代碼示例：
function backtrack(n, used) { // 判斷輸入或者狀態是否非法 if (input/state is invalid) { return; } // 判讀遞歸是否應當結束，滿足結束條件就返回結果 if (match condition) { return some value; } // 遍歷當前所有可能出現的情況，并嘗試每一種情況 for (all possible cases) { // 如果上一步嘗試會影響下一步嘗試，需要寫入狀態 used.push(case) // 遞歸進行下一步嘗試，搜索該子樹 result = backtrack(n + 1, used) // 在這種情況下已經嘗試完畢，重置狀態，以便于下面的回溯嘗試 used.pop(case) } }基本思想：從某頂點出發，沿圖的邊到達另一頂點所經過的路徑中，各邊上權值之和最小的一條路徑叫做最短路徑。解決最短路的問題有以下算法，Dijkstra 算法，Bellman-Ford 算法，Floyd 算法和 SPFA 算法等。
應用場景：應用有計算機網絡路由算法，機器人探路，交通路線導航，人工智能，游戲設計等。
步驟：(Dijkstra 算法示例)
1、 訪問路網中里起始點最近且沒有被檢查過的點，把這個點放入 OPEN 組中等待檢查。
2、 從OPEN表中找出距起始點最近的點，找出這個點的所有子節點，把這個點放到 CLOSE 表中。
3、 遍歷考察這個點的子節點。求出這些子節點距起始點的距離值，放子節點到 OPEN 表中。
4、重復2，3，步。直到 OPEN 表為空，或找到目標點。
代碼示例：
//Dijkstra 算法 static int[] pathSrc = new int[9]; static int[] shortPath = new int[9]; static void shortestPath_DijkStra(MGraph m, int v0) { // finalPath[w] = 1 表示已經獲取到頂點V0到Vw的最短路徑 int[] finalPath = new int[9]; for (int i = 0; i < m.numVertexes; i++) { finalPath[i] = 0; shortPath[i] = m.arc[v0][i]; pathSrc[i] = 0; } // v0到v0的路徑為0 shortPath[v0] = 0; // vo到v0不需要求路徑 finalPath[v0] = 1; for (int i = 1; i < m.numVertexes; i++) { // 當前所知的離V0最近的距離 int min = INFINITY; int k = 0; for (int w = 0; w < m.numVertexes; w++) { if(shortPath[w] < min && finalPath[w] == 0) { min = shortPath [w]; k = w; } } finalPath[k] = 1; // 修改finalPath的值，標記為已經找到最短路徑 for (int w = 0; w < m.numVertexes; w++) { // 如果經過V頂點的路徑比原來的路徑（不經過V）短的話 if(finalPath[w] == 0 && (min + m.arc[k][w]) < shortPath[w]) { // 說明找到了更短的路徑，修改 shortPath[w] = min + m.arc[k][w]; // 修改路徑的長度 pathSrc[w] = k; // 修改頂點下標W的前驅頂點 } } } }基本思想：給定一個整數數組 nums ，找到一個具有最大和的連續子數組(子數組最少包含一個元素)，返回其最大和。
應用場景：生活中可以用來查看股票一周之內的增長狀態，需要得到最合適的買入和賣出時間。
步驟：
1、將子串和為負數的子串丟掉，只留和為正的子串。
2、如果 nums 中有正數，從左到右遍歷 nums，用變量 cur 記錄每一步的累加和，遍歷到正數 cur 增加，遍歷到負數 cur 減少。
3、當 cur>=0 時，每一次累加都可能是最大的累加和，所以，用另外一個變量 max 全程跟蹤記錄 cur 出現的最大值即可。
代碼示例：
class Solution { public: /* * @param nums: A list of integers * @return: A integer indicate the sum of max subarray */ int maxSubArray(vector<int> nums) { if(nums.size()<=0){ return 0; } int max=INT_MIN,cur=0;//c++最小值 for(int i=0; i<nums.size(); i++) { if(cur < 0) cur = nums[i];//如果前面加起來的和小于0，拋棄前面的 else cur+=nums[i]; if(cur > max) max = cur; } return max; } };基本思想：最長公共子序列是一個在一個序列集合中用來查找所有序列中最長子序列的問題。這與查找最長公共子串的問題不同的地方是：子序列不需要在原序列中占用連續的位置。
應用場景：最長公共子序列問題是一個經典的計算機科學問題，也是數據比較程序，比如 Diff 工具，和生物信息學應用的基礎。它也被廣泛地應用在版本控制，比如 Git 用來調和文件之間的改變。
步驟：
1、可以使用遞歸去解決，需要遍歷出所有的可能，很慢;
2、對于一般的 LCS 問題，都屬于 NP 問題;
3、當數列的量為一定的時，都可以采用動態規劃去解決。
代碼示例：
class Solution { public int longestCommonSubsequence(String text1, String text2) { int length2 = text1.length(); int length3 = text2.length(); int[][] a = new int[length2 + 1][length3 + 1];//0行0列保留 for(int i = 1; i <= length2; i++){ for(int j = 1; j <= length3; j++){ if (text1.charAt(i - 1) == text2.charAt(j - 1)) { a[i][j] = a[i - 1][j - 1] + 1; } else { if (a[i][j - 1] > a[i-1][j]) { a[i][j] = a[i][j - 1]; } else { a[i][j] = a[i - 1][j]; } } } } return a[length2][length3]; } }基本思想：在含有n個頂點的帶權無向連通圖中選擇n-1條邊，構成一棵極小連通子圖，并使該連通子圖中n-1條邊上權值之和達到最小，則稱其為連通網的最小生成樹(不一定唯一)。
一般情況，要解決最小生成樹問題，通常采用兩種算法：Prim算法和Kruskal算法。
應用場景：一般用來計算成本最小化的情況。
步驟：(Prim 算法示例)
1、以某一個點開始，尋找當前該點可以訪問的所有的邊;
2、在已經尋找的邊中發現最小邊，這個邊必須有一個點還沒有訪問過，將還沒有訪問的點加入我們的集合，記錄添加的邊;
3、尋找當前集合可以訪問的所有邊，重復 2 的過程，直到沒有新的點可以加入;
4、此時由所有邊構成的樹即為最小生成樹。
代碼示例：
/** prim算法 * @param first 構成最小生成樹的起點的標識 * @return 返回最小生成樹構成的邊 */ public List<Edge> generateMinTreePrim(T first){ //存儲最小生成樹構成的邊 List<Edge> result=new LinkedList<>(); //首先建立map，key為vertex，value為edge HashMap<Vertex<T>, Edge> map=new HashMap<>(); Iterator<Vertex<T>> vertexIterator=getVertexIterator(); Vertex<T> vertex; Edge edge; while(vertexIterator.hasNext()){ //一開始，value為edge的兩端的都為自己，weight=maxDouble vertex=vertexIterator.next(); edge=new Edge(vertex, vertex, Double.MAX_VALUE); map.put(vertex, edge); } //first是構成最小生成樹的起點的標識 vertex=vertexMap.get(first); if(vertex==null){ System.out.println("沒有節點："+first); return result; } //所有不在生成樹中的節點，都是map的key,如果map為空，代表所有節點都在樹中 while(!map.isEmpty()){ //這次循環要加入生成樹的節點為vertex，邊為vertex對應的edge（也就是最小的邊） edge=map.get(vertex); //每將一個結點j加入了樹A，首先從map中去除這個節點 map.remove(vertex); result.add(edge); System.out.println("生成樹加入邊，頂點："+vertex.getLabel()+ " ，邊的終點是："+edge.getEndVertex().getLabel()+" ，邊的權值為： "+edge.getWeight());; //如果是第一個節點，對應的邊是到自己的，刪除 if(vertex.getLabel().equals(first)){ result.remove(edge); } //然后看map中剩余的節點到節點j的距離，如果這個邊的距離小于之前邊的距離，就將邊替換成這個到節點j的邊 //在遍歷替換中，同時發現距離最短的邊minEdge Edge minEdge=new Edge(vertex, vertex, Double.MAX_VALUE); for(Vertex<T> now:map.keySet()){ edge=map.get(now); //newEdge為now到節點j的邊 Edge newEdge=now.hasNeighbourVertex(vertex); if(newEdge!=null&&newEdge.getWeight()<edge.getWeight()){ //如果這個邊的距離小于之前邊的距離，就將邊替換成這個到節點j的邊 edge=newEdge; map.put(now, edge); } if(edge.getWeight()<minEdge.getWeight()){ //更新minEdge minEdge=edge; } } //這里設定邊的方向是不在樹上的v（為起始點）到樹上的u //這條邊的起始點是不在樹上的，是下一個加入生成樹的節點 vertex=minEdge.getBeginVertex(); } return result; }到此，關于“如何使用Java二分查找”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
