摘要：递归实现不考虑相同数二分查找，不考虑有相同数的情况递归找到了考虑有相同数二分查找考虑有相同元素的情况递归要查找的值
/** * 二分查找，不考虑有相同数的情况（递归） * @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; } } }}文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/120965.html
摘要：应用分治法是一种很重要的算法。字面上的解释是分而治之，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。 ...
摘要：问题胜利乡有个村庄现在需要修路把个村庄连通各个村庄的距离用边线表示权比如距离公里问如何修路保证各个村庄都能连通并且总的修建公路总里程最短代码重点理解中的三层循环 问...
摘要：学习资料迪杰斯特拉计算的是单源最短路径，而弗洛伊德计算的是多源最短路径代码不能设置为，否则两个相加会溢出导致出现负权创建顶点和边 学习资料 迪杰斯特拉计算的是单源最...
摘要：例题假设存在如下表的需要付费的广播台，以及广播台信号可以覆盖的地区。 例题 假设存在如下表的需要付费的广播台，以及广播台信号可以覆盖的地区。如何选择最少的广播台，让...
摘要：骑士周游问题又叫马踏棋盘问题未优化前没有策略定义棋盘的行数和列数定义棋盘上的某个点是否被访问过记录是否周游结束从第一行第一列开始走，第一次走算第一步，即展示下是棋盘， ...
阅读 2303·2021-09-28 09:45
阅读 3595·2021-09-24 09:48
阅读 2255·2021-09-22 15:49
阅读 3092·2021-09-08 16:10
阅读 1585·2019-08-30 15:54
阅读 2316·2019-08-30 15:53
阅读 3012·2019-08-29 18:42
阅读 2863·2019-08-29 16:19
