如何使用Java二分查找

這篇文章主要介紹“如何使用Java二分查找”，在日常操作中，相信很多人在如何使用Java二分查找問(wèn)題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”如何使用Java二分查找”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！

創(chuàng)新互聯(lián)專(zhuān)業(yè)提供成都主機(jī)托管四川主機(jī)托管成都服務(wù)器托管四川服務(wù)器托管，支持按月付款！我們的承諾：貴族品質(zhì)、平民價(jià)格，機(jī)房位于中國(guó)電信/網(wǎng)通/移動(dòng)機(jī)房，成都服務(wù)器托管服務(wù)有保障！

二分查找

簡(jiǎn)介

基本思想：又叫折半查找，要求待查找的序列有序，是一種快速查找算法，時(shí)間復(fù)雜度為 O(logn)，要求數(shù)據(jù)集為一個(gè)有序數(shù)據(jù)集。

使用

應(yīng)用場(chǎng)景：一般用于查找數(shù)組元素，并且數(shù)組在查找之前必須已經(jīng)排好序(一般是升序)。

步驟：

1、取中間位置的值與待查關(guān)鍵字比較，如果中間位置的值比待查關(guān)鍵字大，則在前半部分循環(huán)這個(gè)查找的過(guò)程，

2、如果中間位置的值比待查關(guān)鍵字小，則在后半部分循環(huán)這個(gè)查找的過(guò)程。

3、直到查找到了為止，否則序列中沒(méi)有待查的關(guān)鍵字。

代碼示例：

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; }

冒泡排序算法

簡(jiǎn)介

基本思想：比較前后相鄰的兩個(gè)數(shù)據(jù)，如果前面數(shù)據(jù)大于后面的數(shù)據(jù)，就將這二個(gè)數(shù)據(jù)交換。這樣對(duì)數(shù)組的第 0 個(gè)數(shù)據(jù)到 N-1  個(gè)數(shù)據(jù)進(jìn)行一次遍歷后，最大的一個(gè)數(shù)據(jù)就“沉”到數(shù)組第 N-1 個(gè)位置。N=N-1，如果 N 不為 0 就重復(fù)前面二步，否則排序完成。

使用

應(yīng)用場(chǎng)景：數(shù)據(jù)量不大，對(duì)穩(wěn)定性有要求，且數(shù)據(jù)基本有序的情況。

步驟：

1、將序列中所有元素兩兩比較，將最大的放在最后面。

2、將剩余序列中所有元素兩兩比較，將最大的放在最后面。

3、重復(fù)第二步，直到只剩下一個(gè)數(shù)。

代碼示例：

public static void bubbleSort1(int [] a, int n){     int i, j;     for(i=0; i<n; i++){//表示 n 次排序過(guò)程。         for(j=1; j<n-i; j++){             if(a[j-1] > a[j]){//前面的數(shù)字大于后面的數(shù)字就交換                 //交換 a[j-1]和 a[j]                 int temp;                 temp = a[j-1];                 a[j-1] = a[j];                 a[j]=temp;             }      }   } }

插入排序算法

簡(jiǎn)介

基本思想：通過(guò)構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)的位置并插入。

使用

應(yīng)用場(chǎng)景：數(shù)據(jù)量不大，對(duì)算法的穩(wěn)定性有要求，且數(shù)據(jù)局部或者整體有序的情況。

步驟：

1、將第一待排序序列第一個(gè)元素看做一個(gè)有序序列，把第二個(gè)元素到最后一個(gè)元素當(dāng)成是未排序序列。

2、從頭到尾依次掃描未排序序列，將掃描到的每個(gè)元素插入有序序列的適當(dāng)位置。(如果待插入的元素與有序序列中的某個(gè)元素相等，則將待插入元素插入到相等元素的后面。)

代碼示例：

public class InsertSort implements IArraySort {      @Override     public int[] sort(int[] sourceArray) throws Exception {         // 對(duì) arr 進(jìn)行拷貝，不改變參數(shù)內(nèi)容         int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);          // 從下標(biāo)為1的元素開(kāi)始選擇合適的位置插入，因?yàn)橄聵?biāo)為0的只有一個(gè)元素，默認(rèn)是有序的         for (int i = 1; i < arr.length; i++) {              // 記錄要插入的數(shù)據(jù)             int tmp = arr[i];              // 從已經(jīng)排序的序列最右邊的開(kāi)始比較，找到比其小的數(shù)             int j = i;             while (j > 0 && tmp < arr[j - 1]) {                 arr[j] = arr[j - 1];                 j--;             }              // 存在比其小的數(shù)，插入             if (j != i) {                 arr[j] = tmp;             }          }         return arr;     } } 快速排序算法

快速排序算法

簡(jiǎn)介

基本思想：選擇一個(gè)關(guān)鍵值作為基準(zhǔn)值。比基準(zhǔn)值小的都在左邊序列(一般是無(wú)序的)，比基準(zhǔn)值大的都在右邊(一般是無(wú)序的)。一般選擇序列的第一個(gè)元素。

使用

應(yīng)用場(chǎng)景：數(shù)值范圍較大，相同值的概率較小，數(shù)據(jù)量大且不考慮穩(wěn)定性的情況，數(shù)值遠(yuǎn)大于數(shù)據(jù)量時(shí)威力更大。

步驟：

1、一次循環(huán)，從后往前比較，用基準(zhǔn)值和最后一個(gè)值比較，如果比基準(zhǔn)值小的交換位置，如果沒(méi)有繼續(xù)比較下一個(gè)，直到找到第一個(gè)比基準(zhǔn)值小的值才交換。

2、找到這個(gè)值之后，又從前往后開(kāi)始比較，如果有比基準(zhǔn)值大的，交換位置，如果沒(méi)有繼續(xù)比較下一個(gè)，直到找到第一個(gè)比基準(zhǔn)值大的值才交換。

3、直到從前往后的比較索引 > 從后往前比較的索引，結(jié)束第一次循環(huán)，此時(shí)，對(duì)于基準(zhǔn)值來(lái)說(shuō)，左右兩邊就是有序的了。

代碼示例：

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)                  //如果沒(méi)有比關(guān)鍵值小的，比較下一個(gè)，直到有比關(guān)鍵值小的交換位置，然后又從前往后比較                 end--;             if(a[end]<=key){                 int temp = a[end];                 a[end] = a[start];                 a[start] = temp;             }             //從前往后比較             while(end>start&&a[start]<=key)                 //如果沒(méi)有比關(guān)鍵值大的，比較下一個(gè)，直到有比關(guān)鍵值大的交換位置                 start++;             if(a[start]>=key){                 int temp = a[start];                 a[start] = a[end];                 a[end] = temp;             }         //此時(shí)第一次循環(huán)比較結(jié)束，關(guān)鍵值的位置已經(jīng)確定了。左邊的值都比關(guān)鍵值小，右邊的值都比關(guān)鍵值大，但是兩邊的順序還有可能是不一樣的，進(jìn)行下面的遞歸調(diào)用         }         //遞歸         if(start>low) sort(a,low,start-1);//左邊序列。第一個(gè)索引位置到關(guān)鍵值索引-1         if(end<high) sort(a,end+1,high);//右邊序列。從關(guān)鍵值索引+1 到最后一個(gè)     } }

希爾排序算法

簡(jiǎn)介

基本思想：先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行依次直接插入排序。

使用

應(yīng)用場(chǎng)景：數(shù)據(jù)量較大，不要求穩(wěn)定性的情況。

步驟：

1、選擇一個(gè)增量序列 t1，t2，…，tk，其中 ti>tj，tk=1;

2、按增量序列個(gè)數(shù) k，對(duì)序列進(jìn)行 k 趟排序;

3、每趟排序，根據(jù)對(duì)應(yīng)的增量 ti，將待排序列分割成若干長(zhǎng)度為 m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為1  時(shí)，整個(gè)序列作為一個(gè)表來(lái)處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。

代碼示例：

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) {     //類(lèi)似插入排序，只是插入排序增量是 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){                 //通過(guò)循環(huán)，逐個(gè)后移一位找到要插入的位置。                 a[j+dk]=a[j];             }             a[j+dk]=x;//插入         }   } } 歸并排序算法

歸并排序算法

簡(jiǎn)介

基本思想：歸并(Merge)排序法是將兩個(gè)(或兩個(gè)以上)有序表合并成一個(gè)新的有序表，即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的。然后再把有序子序列合并為整體有序序列。

場(chǎng)景使用

應(yīng)用場(chǎng)景：內(nèi)存少的時(shí)候使用，可以進(jìn)行并行計(jì)算的時(shí)候使用。

步驟：

1、選擇相鄰兩個(gè)數(shù)組成一個(gè)有序序列。

2、選擇相鄰的兩個(gè)有序序列組成一個(gè)有序序列。

3、重復(fù)第二步，直到全部組成一個(gè)有序序列。

代碼示例：

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("排序后的數(shù)組：");          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;          // 對(duì)左邊數(shù)組進(jìn)行遞歸         sort(data, left, center);          // 對(duì)右邊數(shù)組進(jìn)行遞歸         sort(data, center + 1, right);          // 合并         merge(data, left, center, right);          print(data);      }       /**      * 將兩個(gè)數(shù)組進(jìn)行歸并，歸并前面 2 個(gè)數(shù)組已有序，歸并后依然有序     * @param data      * 數(shù)組對(duì)象     * @param left      * 左數(shù)組的第一個(gè)元素的索引     * @param center      * 左數(shù)組的最后一個(gè)元素的索引，center+1 是右數(shù)組第一個(gè)元素的索引     * @param right      * 右數(shù)組最后一個(gè)元素的索引     */      public static void merge(int[] data, int left, int center, int right) {          // 臨時(shí)數(shù)組         int[] tmpArr = new int[data.length];          // 右數(shù)組第一個(gè)元素索引         int mid = center + 1;          // third 記錄臨時(shí)數(shù)組的索引         int third = left;          // 緩存左數(shù)組第一個(gè)元素的索引         int tmp = left;          while (left <= center && mid <= right) {              // 從兩個(gè)數(shù)組中取出最小的放入臨時(shí)數(shù)組             if (data[left] <= data[mid]) {                  tmpArr[third++] = data[left++];              } else {                  tmpArr[third++] = data[mid++];              }          }          // 剩余部分依次放入臨時(shí)數(shù)組（實(shí)際上兩個(gè) while 只會(huì)執(zhí)行其中一個(gè)）         while (mid <= right) {              tmpArr[third++] = data[mid++];          }          while (left <= center) {              tmpArr[third++] = data[left++];          }          // 將臨時(shí)數(shù)組中的內(nèi)容拷貝回原數(shù)組中         // （原 left-right 范圍的內(nèi)容被復(fù)制回原數(shù)組）         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();      }  }

桶排序算法

簡(jiǎn)介

基本思想： 把數(shù)組 arr 劃分為 n 個(gè)大小相同子區(qū)間(桶)，每個(gè)子區(qū)間各自排序，最后合并  。計(jì)數(shù)排序是桶排序的一種特殊情況，可以把計(jì)數(shù)排序當(dāng)成每個(gè)桶里只有一個(gè)元素的情況。

使用

應(yīng)用場(chǎng)景：在數(shù)據(jù)量非常大，而空間相對(duì)充裕的時(shí)候是很實(shí)用的，可以大大降低算法的運(yùn)算數(shù)量級(jí)。

步驟：

1、找出待排序數(shù)組中的最大值 max、最小值 min

2、我們使用動(dòng)態(tài)數(shù)組 ArrayList 作為桶，桶里放的元素也用 ArrayList 存儲(chǔ)。桶的數(shù)量為(maxmin)/arr.length+1

3、遍歷數(shù)組 arr，計(jì)算每個(gè)元素 arr[i] 放的桶

4、每個(gè)桶各自排序

代碼示例：

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]);     }     //創(chuàng)建桶     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>());     }     //將每個(gè)元素放入桶     for(int i = 0; i < arr.length; i++){         int num = (arr[i] - min) / (arr.length);         bucketArr.get(num).add(arr[i]);     }     //對(duì)每個(gè)桶進(jìn)行排序     for(int i = 0; i < bucketArr.size(); i++){         Collections.sort(bucketArr.get(i));     } }

基數(shù)排序算法

簡(jiǎn)介

基本思想：將所有待比較數(shù)值(正整數(shù))統(tǒng)一為同樣的數(shù)位長(zhǎng)度，數(shù)位較短的數(shù)前面補(bǔ)零。然后，從最低位開(kāi)始，依次進(jìn)行一次排序。這樣從最低位排序一直到最高位排序完成以后,數(shù)列就變成一個(gè)有序序列。

使用

應(yīng)用場(chǎng)景：用于大量數(shù)，很長(zhǎng)的數(shù)進(jìn)行排序時(shí)的情況。

步驟：

1、將所有的數(shù)的個(gè)位數(shù)取出，按照個(gè)位數(shù)進(jìn)行排序，構(gòu)成一個(gè)序列。

2、將新構(gòu)成的所有的數(shù)的十位數(shù)取出，按照十位數(shù)進(jìn)行排序，構(gòu)成一個(gè)序列。

代碼示例：

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){         //首先確定排序的趟數(shù);         int max=array[0];         for(inti=1;i<array.length;i++){             if(array[i]>max){                 max=array[i];             }     }         int time=0;         //判斷位數(shù);         while(max>0){             max/=10;             time++;         }         //建立 10 個(gè)隊(duì)列;         List<ArrayList> queue=newArrayList<ArrayList>();         for(int i=0;i<10;i++){             ArrayList<Integer>queue1=new ArrayList<Integer>();             queue.add(queue1);         }         //進(jìn)行 time 次分配和收集;         for(int i=0;i<time;i++){             //分配數(shù)組元素;            for(intj=0;j<array.length;j++){                 //得到數(shù)字的第 time+1 位數(shù);                 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;//元素計(jì)數(shù)器;             //收集隊(duì)列元素;             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++;                 }       }     }   } }

剪枝算法

簡(jiǎn)介

基本思想：在搜索算法中優(yōu)化中，剪枝，就是通過(guò)某種判斷，避免一些不必要的遍歷過(guò)程，形象的說(shuō)，就是剪去了搜索樹(shù)中的某些“枝條”，故稱(chēng)剪枝。應(yīng)用剪枝優(yōu)化的核心問(wèn)題是設(shè)計(jì)剪枝判斷方法，即確定哪些枝條應(yīng)當(dāng)舍棄，哪些枝條應(yīng)當(dāng)保留的方法。

使用

應(yīng)用場(chǎng)景：通常應(yīng)用在 DFS 和 BFS 搜索算法中，尋找過(guò)濾條件，提前減少不必要的搜索路徑。

步驟：

1、基于訓(xùn)練數(shù)據(jù)集生成決策樹(shù)，生成的決策樹(shù)要盡量大;

2、用驗(yàn)證數(shù)據(jù)集最已生成的樹(shù)進(jìn)行剪枝并選擇最優(yōu)子樹(shù)，這時(shí)用損失函數(shù)最小作為剪枝的標(biāo)準(zhǔn)

代碼示例：

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();         }      } }

回溯算法

簡(jiǎn)介

基本思想：回溯算法實(shí)際上一個(gè)類(lèi)似枚舉的搜索嘗試過(guò)程，主要是在搜索嘗試過(guò)程中尋找問(wèn)題的解，當(dāng)發(fā)現(xiàn)已不滿(mǎn)足求解條件時(shí)，就“回溯”返回，嘗試別的路徑。

使用

應(yīng)用場(chǎng)景：設(shè)置一個(gè)遞歸函數(shù)，函數(shù)的參數(shù)會(huì)攜帶一些當(dāng)前的可能解的信息，根據(jù)這些參數(shù)得出可能解或者不可能而回溯，平時(shí)經(jīng)常見(jiàn)的有 N  皇后、數(shù)獨(dú)、集合等情況。

步驟：

1、定義一個(gè)解空間，它包含問(wèn)題的解;

2、利用適于搜索的方法組織解空間;

3、利用深度優(yōu)先法搜索解空間;

4、利用限界函數(shù)避免移動(dòng)到不可能產(chǎn)生解的子空間。

代碼示例：

function backtrack(n, used) {     // 判斷輸入或者狀態(tài)是否非法     if (input/state is invalid) {         return;       }     // 判讀遞歸是否應(yīng)當(dāng)結(jié)束，滿(mǎn)足結(jié)束條件就返回結(jié)果     if (match condition) {         return some value;       }     // 遍歷當(dāng)前所有可能出現(xiàn)的情況，并嘗試每一種情況     for (all possible cases) {         // 如果上一步嘗試會(huì)影響下一步嘗試，需要寫(xiě)入狀態(tài)         used.push(case)         // 遞歸進(jìn)行下一步嘗試，搜索該子樹(shù)         result = backtrack(n + 1, used)         // 在這種情況下已經(jīng)嘗試完畢，重置狀態(tài)，以便于下面的回溯嘗試         used.pop(case)     }  }

最短路徑算法

簡(jiǎn)介

基本思想：從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過(guò)的路徑中，各邊上權(quán)值之和最小的一條路徑叫做最短路徑。解決最短路的問(wèn)題有以下算法，Dijkstra  算法，Bellman-Ford 算法，F(xiàn)loyd 算法和 SPFA 算法等。

使用

應(yīng)用場(chǎng)景：應(yīng)用有計(jì)算機(jī)網(wǎng)絡(luò)路由算法，機(jī)器人探路，交通路線(xiàn)導(dǎo)航，人工智能，游戲設(shè)計(jì)等。

步驟：(Dijkstra 算法示例)

1、 訪(fǎng)問(wèn)路網(wǎng)中里起始點(diǎn)最近且沒(méi)有被檢查過(guò)的點(diǎn)，把這個(gè)點(diǎn)放入 OPEN 組中等待檢查。

2、 從OPEN表中找出距起始點(diǎn)最近的點(diǎn)，找出這個(gè)點(diǎn)的所有子節(jié)點(diǎn)，把這個(gè)點(diǎn)放到 CLOSE 表中。

3、 遍歷考察這個(gè)點(diǎn)的子節(jié)點(diǎn)。求出這些子節(jié)點(diǎn)距起始點(diǎn)的距離值，放子節(jié)點(diǎn)到 OPEN 表中。

4、重復(fù)2，3，步。直到 OPEN 表為空，或找到目標(biāo)點(diǎn)。

代碼示例：

//Dijkstra 算法 static int[] pathSrc = new int[9]; static int[] shortPath = new int[9]; static void shortestPath_DijkStra(MGraph m, int v0) {         // finalPath[w] = 1 表示已經(jīng)獲取到頂點(diǎn)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++) {                 // 當(dāng)前所知的離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的值，標(biāo)記為已經(jīng)找到最短路徑         for (int w = 0; w < m.numVertexes; w++) {                         // 如果經(jīng)過(guò)V頂點(diǎn)的路徑比原來(lái)的路徑（不經(jīng)過(guò)V）短的話(huà)                         if(finalPath[w] == 0 && (min + m.arc[k][w]) < shortPath[w]) {                        // 說(shuō)明找到了更短的路徑，修改                                 shortPath[w] = min + m.arc[k][w]; // 修改路徑的長(zhǎng)度                 pathSrc[w] = k; // 修改頂點(diǎn)下標(biāo)W的前驅(qū)頂點(diǎn)             }                 }         } }

最大子數(shù)組算法

簡(jiǎn)介

基本思想：給定一個(gè)整數(shù)數(shù)組 nums ，找到一個(gè)具有最大和的連續(xù)子數(shù)組(子數(shù)組最少包含一個(gè)元素)，返回其最大和。

使用

應(yīng)用場(chǎng)景：生活中可以用來(lái)查看股票一周之內(nèi)的增長(zhǎng)狀態(tài)，需要得到最合適的買(mǎi)入和賣(mài)出時(shí)間。

步驟：

1、將子串和為負(fù)數(shù)的子串丟掉，只留和為正的子串。

2、如果 nums 中有正數(shù)，從左到右遍歷 nums，用變量 cur 記錄每一步的累加和，遍歷到正數(shù) cur 增加，遍歷到負(fù)數(shù) cur 減少。

3、當(dāng) cur>=0 時(shí)，每一次累加都可能是最大的累加和，所以，用另外一個(gè)變量 max 全程跟蹤記錄 cur 出現(xiàn)的最大值即可。

代碼示例：

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];//如果前面加起來(lái)的和小于0，拋棄前面的             else                 cur+=nums[i];              if(cur > max)                 max = cur;         }           return max;        } };

最長(zhǎng)公共子序算法

簡(jiǎn)介

基本思想：最長(zhǎng)公共子序列是一個(gè)在一個(gè)序列集合中用來(lái)查找所有序列中最長(zhǎng)子序列的問(wèn)題。這與查找最長(zhǎng)公共子串的問(wèn)題不同的地方是：子序列不需要在原序列中占用連續(xù)的位置。

使用

應(yīng)用場(chǎng)景：最長(zhǎng)公共子序列問(wèn)題是一個(gè)經(jīng)典的計(jì)算機(jī)科學(xué)問(wèn)題，也是數(shù)據(jù)比較程序，比如 Diff 工具，和生物信息學(xué)應(yīng)用的基礎(chǔ)。它也被廣泛地應(yīng)用在版本控制，比如  Git 用來(lái)調(diào)和文件之間的改變。

步驟：

1、可以使用遞歸去解決，需要遍歷出所有的可能，很慢;

2、對(duì)于一般的 LCS 問(wèn)題，都屬于 NP 問(wèn)題;

3、當(dāng)數(shù)列的量為一定的時(shí)，都可以采用動(dòng)態(tài)規(guī)劃去解決。

代碼示例：

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];     } }

最小生成樹(shù)算法

簡(jiǎn)介

基本思想：在含有n個(gè)頂點(diǎn)的帶權(quán)無(wú)向連通圖中選擇n-1條邊，構(gòu)成一棵極小連通子圖，并使該連通子圖中n-1條邊上權(quán)值之和達(dá)到最小，則稱(chēng)其為連通網(wǎng)的最小生成樹(shù)(不一定唯一)。

一般情況，要解決最小生成樹(shù)問(wèn)題，通常采用兩種算法：Prim算法和Kruskal算法。

使用

應(yīng)用場(chǎng)景：一般用來(lái)計(jì)算成本最小化的情況。

步驟：(Prim 算法示例)

1、以某一個(gè)點(diǎn)開(kāi)始，尋找當(dāng)前該點(diǎn)可以訪(fǎng)問(wèn)的所有的邊;

2、在已經(jīng)尋找的邊中發(fā)現(xiàn)最小邊，這個(gè)邊必須有一個(gè)點(diǎn)還沒(méi)有訪(fǎng)問(wèn)過(guò)，將還沒(méi)有訪(fǎng)問(wèn)的點(diǎn)加入我們的集合，記錄添加的邊;

3、尋找當(dāng)前集合可以訪(fǎng)問(wèn)的所有邊，重復(fù) 2 的過(guò)程，直到?jīng)]有新的點(diǎn)可以加入;

4、此時(shí)由所有邊構(gòu)成的樹(shù)即為最小生成樹(shù)。

代碼示例：

/** prim算法     * @param first  構(gòu)成最小生成樹(shù)的起點(diǎn)的標(biāo)識(shí)     * @return  返回最小生成樹(shù)構(gòu)成的邊     */ public List<Edge> generateMinTreePrim(T first){     //存儲(chǔ)最小生成樹(shù)構(gòu)成的邊     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()){         //一開(kāi)始，value為edge的兩端的都為自己，weight=maxDouble         vertex=vertexIterator.next();         edge=new Edge(vertex, vertex, Double.MAX_VALUE);         map.put(vertex, edge);     }     //first是構(gòu)成最小生成樹(shù)的起點(diǎn)的標(biāo)識(shí)     vertex=vertexMap.get(first);     if(vertex==null){         System.out.println("沒(méi)有節(jié)點(diǎn)："+first);         return result;     }     //所有不在生成樹(shù)中的節(jié)點(diǎn)，都是map的key,如果map為空，代表所有節(jié)點(diǎn)都在樹(shù)中     while(!map.isEmpty()){         //這次循環(huán)要加入生成樹(shù)的節(jié)點(diǎn)為vertex，邊為vertex對(duì)應(yīng)的edge（也就是最小的邊）         edge=map.get(vertex);         //每將一個(gè)結(jié)點(diǎn)j加入了樹(shù)A，首先從map中去除這個(gè)節(jié)點(diǎn)         map.remove(vertex);         result.add(edge);         System.out.println("生成樹(shù)加入邊，頂點(diǎn)："+vertex.getLabel()+                 " ，邊的終點(diǎn)是："+edge.getEndVertex().getLabel()+" ，邊的權(quán)值為： "+edge.getWeight());;         //如果是第一個(gè)節(jié)點(diǎn)，對(duì)應(yīng)的邊是到自己的，刪除         if(vertex.getLabel().equals(first)){             result.remove(edge);         }         //然后看map中剩余的節(jié)點(diǎn)到節(jié)點(diǎn)j的距離，如果這個(gè)邊的距離小于之前邊的距離，就將邊替換成這個(gè)到節(jié)點(diǎn)j的邊         //在遍歷替換中，同時(shí)發(fā)現(xiàn)距離最短的邊minEdge         Edge minEdge=new Edge(vertex, vertex, Double.MAX_VALUE);         for(Vertex<T> now:map.keySet()){             edge=map.get(now);             //newEdge為now到節(jié)點(diǎn)j的邊             Edge newEdge=now.hasNeighbourVertex(vertex);             if(newEdge!=null&&newEdge.getWeight()<edge.getWeight()){                 //如果這個(gè)邊的距離小于之前邊的距離，就將邊替換成這個(gè)到節(jié)點(diǎn)j的邊                 edge=newEdge;                 map.put(now, edge);             }             if(edge.getWeight()<minEdge.getWeight()){                 //更新minEdge                 minEdge=edge;             }         }         //這里設(shè)定邊的方向是不在樹(shù)上的v（為起始點(diǎn)）到樹(shù)上的u         //這條邊的起始點(diǎn)是不在樹(shù)上的，是下一個(gè)加入生成樹(shù)的節(jié)點(diǎn)         vertex=minEdge.getBeginVertex();                 }            return result; }

到此，關(guān)于“如何使用Java二分查找”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！

本文題目：如何使用Java二分查找
網(wǎng)頁(yè)鏈接：http://muchs.cn/article32/ghsjsc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供手機(jī)網(wǎng)站建設(shè)、標(biāo)簽優(yōu)化、品牌網(wǎng)站建設(shè)、網(wǎng)站內(nèi)鏈、品牌網(wǎng)站制作、ChatGPT

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀(guān)點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)