資訊專欄INFORMATION COLUMN
摘要：遞歸實現不考慮相同數二分查找，不考慮有相同數的情況遞歸找到了考慮有相同數二分查找考慮有相同元素的情況遞歸要查找的值
/** * 二分查找，不考慮有相同數的情況（遞歸） * @param arr * @param left * @param right * @param findVal * @return */public static int binarySearch(int[] arr,int left,int right,int findVal){ if (left > right || arr[0] > findVal || arr[arr.length - 1] < findVal){ return -1; }else { int mid = (left + right) / 2; if (arr[mid] > findVal){ return binarySearch(arr,left,mid - 1,findVal); }else if (arr[mid] < findVal){ return binarySearch(arr,mid + 1,right,findVal); }else { //找到了 return mid; } }}/** * 二分查找 考慮有相同元素的情況（遞歸） * @param arr * @param left * @param right * @param findVal 要查找的值 * @return */public static ArrayList<Integer> binarySearch1(int[] arr,int left,int right,int findVal){ if (left > right || arr[0] > findVal || arr[arr.length - 1] < findVal){ return null; }else { int mid = (left + right) / 2; if (arr[mid] > findVal){ return binarySearch1(arr,left,mid - 1,findVal); }else if (arr[mid] < findVal){ return binarySearch1(arr,mid + 1,right,findVal); }else { ArrayList<Integer> arrayList = new ArrayList<>(); //先往左走 int midLeft = mid - 1; while (midLeft >= 0 && arr[midLeft] == findVal){ arrayList.add(midLeft); midLeft--; } Collections.reverse(arrayList); arrayList.add(mid); int midRight = mid + 1; while (midRight < arr.length && arr[midRight] == findVal){ arrayList.add(midRight); midRight++; } return arrayList; } }}/** * 二分查找，不考慮有相同數的情況（非遞歸） * @param arr * @param findVal * @return */public static int binarySearch3(int[] arr,int findVal){ int left = 0; int right = arr.length - 1; while (left <= right){ int mid = (left + right) / 2; if (arr[mid] > findVal){ right = mid - 1; }else if (arr[mid] < findVal){ left = mid + 1; }else { return mid; } } return -1;}/** * 二分查找，考慮有相同數的情況（非遞歸） * @param arr * @param findVal * @return */public static ArrayList<Integer> binarySearch4(int[] arr,int findVal){ int left = 0; int right = arr.length - 1; while (left <= right){ int mid = (left + right) / 2; if (arr[mid] > findVal){ right = mid - 1; }else if (arr[mid] < findVal){ left = mid + 1; }else { ArrayList<Integer> arrayList = new ArrayList<>(); int midLeft = mid - 1; while (midLeft > 0 && arr[midLeft] == findVal){ arrayList.add(midLeft); midLeft--; } Collections.reverse(arrayList); arrayList.add(mid); int midRight = mid + 1; while (midRight < arr.length && arr[midRight] == findVal){ arrayList.add(midRight); midRight++; } return arrayList; } } return new ArrayList<>();}public class Main { public static void main(String[] args) { int[] arr = {1,1,2,2,33}; } /** * 二分查找，考慮有相同數的情況（非遞歸） * @param arr * @param findVal * @return */ public static ArrayList<Integer> binarySearch4(int[] arr,int findVal){ int left = 0; int right = arr.length - 1; while (left <= right){ int mid = (left + right) / 2; if (arr[mid] > findVal){ right = mid - 1; }else if (arr[mid] < findVal){ left = mid + 1; }else { ArrayList<Integer> arrayList = new ArrayList<>(); int midLeft = mid - 1; while (midLeft > 0 && arr[midLeft] == findVal){ arrayList.add(midLeft); midLeft--; } Collections.reverse(arrayList); arrayList.add(mid); int midRight = mid + 1; while (midRight < arr.length && arr[midRight] == findVal){ arrayList.add(midRight); midRight++; } return arrayList; } } return new ArrayList<>(); } /** * 二分查找，不考慮有相同數的情況（非遞歸） * @param arr * @param findVal * @return */ public static int binarySearch3(int[] arr,int findVal){ int left = 0; int right = arr.length - 1; while (left <= right){ int mid = (left + right) / 2; if (arr[mid] > findVal){ right = mid - 1; }else if (arr[mid] < findVal){ left = mid + 1; }else { return mid; } } return -1; } /** * 二分查找 考慮有相同元素的情況（遞歸） * @param arr * @param left * @param right * @param findVal 要查找的值 * @return */ public static ArrayList<Integer> binarySearch1(int[] arr,int left,int right,int findVal){ if (left > right || arr[0] > findVal || arr[arr.length - 1] < findVal){ return null; }else { int mid = (left + right) / 2; if (arr[mid] > findVal){ return binarySearch1(arr,left,mid - 1,findVal); }else if (arr[mid] < findVal){ return binarySearch1(arr,mid + 1,right,findVal); }else { ArrayList<Integer> arrayList = new ArrayList<>(); //先往左走 int midLeft = mid - 1; while (midLeft >= 0 && arr[midLeft] == findVal){ arrayList.add(midLeft); midLeft--; } Collections.reverse(arrayList); arrayList.add(mid); int midRight = mid + 1; while (midRight < arr.length && arr[midRight] == findVal){ arrayList.add(midRight); midRight++; } return arrayList; } } } /** * 二分查找，不考慮有相同數的情況（遞歸） * @param arr * @param left * @param right * @param findVal * @return */ public static int binarySearch(int[] arr,int left,int right,int findVal){ if (left > right || arr[0] > findVal || arr[arr.length - 1] < findVal){ return -1; }else { int mid = (left + right) / 2; if (arr[mid] > findVal){ return binarySearch(arr,left,mid - 1,findVal); }else if (arr[mid] < findVal){ return binarySearch(arr,mid + 1,right,findVal); }else { //找到了 return mid; } } }}文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/120965.html
摘要：應用分治法是一種很重要的算法。字面上的解釋是分而治之，就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。 ...
摘要：問題勝利鄉有個村莊現在需要修路把個村莊連通各個村莊的距離用邊線表示權比如距離公里問如何修路保證各個村莊都能連通并且總的修建公路總里程最短代碼重點理解中的三層循環 問...
摘要：學習資料迪杰斯特拉計算的是單源最短路徑，而弗洛伊德計算的是多源最短路徑代碼不能設置為，否則兩個相加會溢出導致出現負權創建頂點和邊 學習資料 迪杰斯特拉計算的是單源最...
摘要：例題假設存在如下表的需要付費的廣播臺，以及廣播臺信號可以覆蓋的地區。 例題 假設存在如下表的需要付費的廣播臺，以及廣播臺信號可以覆蓋的地區。如何選擇最少的廣播臺，讓...
摘要：騎士周游問題又叫馬踏棋盤問題未優化前沒有策略定義棋盤的行數和列數定義棋盤上的某個點是否被訪問過記錄是否周游結束從第一行第一列開始走，第一次走算第一步，即展示下是棋盤， ...
閱讀 2305·2021-09-28 09:45
閱讀 3596·2021-09-24 09:48
閱讀 2256·2021-09-22 15:49
閱讀 3093·2021-09-08 16:10
閱讀 1586·2019-08-30 15:54
閱讀 2316·2019-08-30 15:53
閱讀 3012·2019-08-29 18:42
閱讀 2863·2019-08-29 16:19
