手机网站 像素,创作网,设计一个个人网站的基本步骤,电子邮箱怎么申请概述
二分查找算法的应用#xff0c;包括有序和无序数据#xff0c;有序数组默认按从小到大排序
在有序数组中找到num
/*** 4 二分查找 在有序数组中找到num* 思路#xff1a;找中值#xff0c;然后中值元素和目标值比较。如果中值元素比目标值大#xff0c;则继续在左…概述
二分查找算法的应用包括有序和无序数据有序数组默认按从小到大排序
在有序数组中找到num
/*** 4 二分查找 在有序数组中找到num* 思路找中值然后中值元素和目标值比较。如果中值元素比目标值大则继续在左半区域查找。反之右半区。重复该过程直至找到目标值* param arr 数组* param num 目标值* return 返回目标值的索引*/public static int binarySearch(int[] arr, int num){// 边界条件if(arr null){return -1;}int l 0;int r arr.length-1;while(l r){int mid l (r-l)/2;if(arr[mid] num){return mid;} else if (arr[mid] num) {// 去左半区找r mid - 1;} else{// 去右半区找l mid 1;}}return -1;}在有序数组中找到最左边num的元素位置
/*** 5 二分查找在有序数组中找到num最左的位置* 思路在原来的二分查找基础上找到处于最左位置的target。* 每次二分找到目标值时用临时变量记录此时的索引。再查找左半区是否还有target如果有则更新临时变量。* param arr 数组* param num 目标值* return 最左位置的索引*/public static int binarySearch2(int[] arr, int num){// 边界条件if(arr null){return -1;}int l 0;int r arr.length-1;int ans -1;while(l r){int mid l (r-l)/2;if(arr[mid] num){ans mid;r mid-1;}else{l mid1;}}return ans;}在有序数组中找到最右边num的元素位置 /*** 6 二分查找在有序数组中找到num的最右边的位置* 思路二分得到中值如果中值元素目标值则检查中值的右边是否还有满足目标值的元素。反之查中值的左边。* param arr 数组* param num 目标值* return 目标值的索引*/public static int binarySearch3(int[] arr, int num){// 边界条件if(arr null || arr.length 1){return -1;}int l 0;int r arr.length-1;int ans -1;while(l r){int mid l (r-l)/2;if(arr[mid] num){ans mid;l mid 1;}else{r mid - 1;}}return ans;}logn时间复杂度的无序数组寻找局部最值
/*** 寻找峰值a hrefhttps://leetcode.cn/problems/find-peak-element/description/.../a* 在无序相邻元素不相等的列表中返回任一局部最小值* 思路通过二分降低时间复杂度提升效率。找到中值后判断中值元素临近的mid-1、mid1的关系。* 最值要么出现在数组两端要么出现在中间。* 在无序数组中找到中值后如果arr[mid-1] arr[mid] arr[mid1]那么在0-mid之间一定存在一个最小值。* 所以剩下就是二分找到这个最小值。* author Kenyi*/
public class LocalMinValue {public static void main(String[] args) {int length 9;int maxValue 10;int testCycle 100000;for (int i 0; i testCycle; i) {int[] arr randomArray(length, maxValue);int minIndex binarySearchValleyElement(arr);if(!check(arr, minIndex)){System.out.println(出错了);System.out.println(minIndex: minIndex);printArr(arr);}}}/*** 8 二分查找局部最小值算法* param arr 数组* return 目标值索引*/public static int binarySearchValleyElement(int[] arr){// 边界条件if(arr null ){return -1;}int length arr.length;if(length 0){return -1;}if(length 1){return 0;}if(arr[0] arr[1]){return 0;}if(arr[length -1] arr[length -2]){return length -1;}int left 0;int right length -1;while(left right){int mid left (right - left)/2;if(arr[mid-1] arr[mid]){right mid-1;} else if (arr[mid] arr[mid1]) {left mid1;}else{return mid;}}return -1;}/*** 返回数组任一的局部最大值* param arr 数组* return 局部最大值的索引*/public static int findPeakElement(int[] arr) {int n arr.length;if (arr.length 1) {return 0;}if (arr[0] arr[1]) {return 0;}if (arr[n - 1] arr[n - 2]) {return n - 1;}int l 1, r n - 2, m 0, ans -1;while (l r) {m (l r) / 2;if (arr[m - 1] arr[m]) {r m - 1;} else if (arr[m] arr[m 1]) {l m 1;} else {ans m;break;}}return ans;}/*** 生成随机数组* param length 数组长度* param maxValue 元素最大值* return 生成的数组*/public static int[] randomArray(int length, int maxValue){// 边界条件int[] arr new int[length];if(length 0){return arr;}arr[0] (int)(Math.random() * maxValue);if(length 1){return arr;}// 相邻元素互不相等for (int i 1; i length; i) {do{arr[i] (int)(Math.random() * maxValue);}while (arr[i] arr[i-1]);}return arr;}/*** 检查是否是局部最小值* param arr 数组* param index 索引* return 布尔值*/public static boolean check(int[] arr, int index){if(arr null || arr.length 0){return index -1;}if(index -1){for (int i 1; i arr.length-1; i) {if(arr[i-1] arr[i] arr[i] arr[i1]){return false;}}return true;}int left index-1;int right index1;boolean leftOk left 0 || arr[left] arr[index];boolean rightOk right arr.length - 1 || arr[index] arr[index 1];return leftOk rightOk;}/*** 打印数组* param arr 数组*/public static void printArr(int[] arr){System.out.println(Arrays.toString(arr));}
