网站建设所需要的软件,比百度好用的搜索软件,做网站设计需要多少钱,wordpress 查看文章引言
二分法#xff0c;顾名思义#xff0c;即一分为二的方法#xff0c;通常用于判断在某个有序数列中是否存在某个数#xff0c;由于其优秀的算法思想#xff0c;时间复杂度一般都是 O(logN) #xff0c;通常要 O(N) 的遍历方式更加优秀。
一、经典二分法查找
最常见…引言
二分法顾名思义即一分为二的方法通常用于判断在某个有序数列中是否存在某个数由于其优秀的算法思想时间复杂度一般都是 O(logN) 通常要 O(N) 的遍历方式更加优秀。
一、经典二分法查找
最常见的二分查找是有序数列找某数但并不是所有二分查找都必须有序。
public static boolean exist(int[] sortedArr, int num) {if (sortedArr null || sortedArr.length 0) return false;// 设置边际int L 0, mid 0, R sortedArr.length - 1;// L .. Rwhile (L R) {// 计算midmid L ((R - L) 1);if (sortedArr[mid] num) {return true;} else if (sortedArr[mid] num) {// 弃右留左R mid - 1;} else {// 弃左留右L mid 1;}}return sortedArr[L] num;
}
二、其他二分查找题目
题目给定一个有序数组找 某数最左侧的位置例如arr{1,2,3,3,3,4,4,6,9},即找到位置 2。
public static int mostLeftIndex(int[] arr, int num) {int L 0, R arr.length - 1;int mostLeftIndex 0;while (L R) {mostLeftIndex L ((R - L) 1);if (arr[mostLeftIndex] num) {// 弃右留左R mostLeftIndex - 1;} else {// 弃左留右L mostLeftIndex 1;}}if (arr[L] num)return L;elsereturn L 1;
}
题目2局部最小问题在无序数组中任意相邻两个数不相等只要比相邻的数都小就是局部最小找到并返回这样一个局部最小值的位置。
例如若[0][1]则[0]就是局部最小[len-2][len-1] 则[len-1]就是局部最小 [i-1][i][i1]那么[i]就是局部最小。
public static int partialMin(int[] arr) {if (arr[0] arr[1])return 0;if (arr[arr.length - 2] arr[arr.length - 1])return arr.length - 1;int L 1;int R arr.length - 2;int mid 0;while (L R) {mid L ((R - L) 1);if (arr[mid] arr[mid 1]) {// 弃左留右L mid 1;} else if (arr[mid] arr[mid - 1]){// 弃右留左R mid - 1;} else {return mid;}}return L;
}
局部最小问题解析首先判断 0 和最后一个位置上的数是否为最小如果都不是那么在两者中间一定存在一个局部最小。二分然后看中间位置是否比一侧大取大于一侧的区间就形成了最开始的“两端都不是最小那么中间一定存在一个最小” 这样的结构。
