帮别人做网站规划,网站建设 应该付多少维护费呢,建网站开发,电子商务网站建设实习文章目录 在有序数组中找num是否存在实现思路实现代码(里面运用了对数器)在有序数组中找num的最左位置实现思路代码实现 在有序数组中找num的最右位置实现思路实现代码 二分搜索不一定发生在有序数组上(比如寻找峰值问题)题目描述实现思路实现代码 在有序数组中找num是… 文章目录 在有序数组中找num是否存在实现思路实现代码(里面运用了对数器)在有序数组中找num的最左位置实现思路代码实现 在有序数组中找num的最右位置实现思路实现代码 二分搜索不一定发生在有序数组上(比如寻找峰值问题)题目描述实现思路实现代码 在有序数组中找num是否存在 实现思路
先定义左索引为0有索引为数组长度-1然后定义中间索引(在左索引和右索引的中间)然后拿num和中间索引对应的数作比较相等的话代表这个数存在。如果num大于中间索引的数因为是有序数组中间索引左边的数都小于等于中间索引的数所以要查找的数的范围是在中间索引右边到右索引里面让其左索引等于中间索引加1然后再从步骤2开始如果要查找的数小于中间索引的数那么应该在左索引到中间索引这个范围内让右索引等于中间索引减1再从步骤2开始
实现代码(里面运用了对数器) public static void main(String[] args) {int N 100;int V 1000;int testTime 500000;System.out.println(测试开始);for (int i 0; i testTime; i) {//[0,1) * 100 [0,100)int n (int) (Math.random() * N);int[] arr randomArray(n, V);Arrays.sort(arr);int num (int) (Math.random() * V);int a right(arr,num);int b getIndex(arr,num);if (a ! b){System.out.println(出错了);}}System.out.println(测试结束);}public static int right(int[] arr, int num) {if (Arrays.binarySearch(arr, num) 0){return Arrays.binarySearch(arr, num) ;}else {return -1;}}public static int getIndex(int[] arr, int num) {if (arr null || arr.length 0) {return -1;}int left 0;int right arr.length - 1;while (left right) {int mid left (right - left) / 2;if (arr[mid] num) {return mid;} else if (arr[mid] num) {right mid - 1;} else {left mid 1;}}return -1;}public static int[] randomArray(int n, int v) {int[] arr new int[n];for (int i 0; i n; i) {//[0,1) * 1000 1 [1,1000]arr[i] (int) (Math.random() * v) 1;}return arr;} 在有序数组中找num的最左位置 实现思路
先定义左索引为0有索引为数组长度-1然后定义中间索引(在左索引和右索引的中间)定义最终一个索引为-1判断中间索引的元素和num的比较情况 num大所以在中间索引右边的区域重复步骤2num小在左边的区域让最终索引等于中间索引看左边区域重复步骤2 返回最终索引
代码实现 public static void main(String[] args) {int N 100;int V 1000;int testTime 500000;System.out.println(测试开始);for (int i 0; i testTime; i) {int n (int) (Math.random() * N);int[] arr randomArray(n, V);Arrays.sort(arr);int num (int) Math.random() * V;if (rightIndex(arr,num) ! getIndex(arr,num)){System.out.println(出错了);}}System.out.println(测试结束);}public static int[] randomArray(int n, int v) {int[] arr new int[n];for (int i 0; i n; i) {arr[i] (int) (Math.random() * v 1);}return arr;}public static int rightIndex(int[] arr, int num) {for (int i 0; i arr.length; i) {if (arr[i] num) {return i;}}return -1;}public static int getIndex(int[] arr, int num) {int left 0;int right arr.length - 1;int ans -1;while (left right) {int mid left (right - left) / 2;if (arr[mid] num){left mid 1;}else {ans mid;right mid -1;}}return ans;}在有序数组中找num的最右位置 实现思路
和上面第二个的思路差不多。用暴力解求索引时让其从后往前遍历然后让其元素小于等于num在通过最优解(二分查找)时中间索引大于num时范围就编程中间索引的左边反之最终索引等于中间索引然后范围在中间索引的右边
实现代码
public static void main(String[] args) {int N 100;int V 1000;int testTime 500000;System.out.println(测试开始);for (int i 0; i testTime; i) {int n (int) (Math.random() * N);int[] arr randomArray(n, V);Arrays.sort(arr);int num (int) Math.random() * V;if (rightIndex(arr,num) ! getIndex(arr,num)){System.out.println(出错了);}}System.out.println(测试结束);}public static int[] randomArray(int n, int v) {int[] arr new int[n];for (int i 0; i n; i) {arr[i] (int) (Math.random() * v 1);}return arr;}public static int rightIndex(int[] arr, int num) {for (int i arr.length - 1; i 0; i--) {if (arr[i] num) {return i;}}return -1;}public static int getIndex(int[] arr, int num) {int left 0;int right arr.length - 1;int ans -1;while (left right) {int mid left (right - left) / 2;if (arr[mid] num){right mid - 1;}else {ans mid;left mid 1;}}return ans;}二分搜索不一定发生在有序数组上(比如寻找峰值问题) 题目描述
峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组 arr找到峰值元素并返回其索引。数组可能包含多个峰值在这种情况下返回任何一个峰值所在位置即可。你可以假设 arr[-1] arr[n] -∞ 。你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
实现思路
先判断数组个数 如果个数为1那么这个数就是峰值返回0索引如果不为1也就是大于等于2 数组长度大于等于2 判断第一个数和第二个数的大小如果第一个数大于第二个数那么第一个数就是峰值判断倒数第一个数和倒数第二个数如果倒数第一个数大于倒数第二个数那么倒数第一个数就是峰值 不属于步骤2的俩个条件那么就可以用二分搜索 定义中间索引判断中间索引数和中间索引数的前一个数如果中间索引数小于中间索引数的前一个数那么中间索引左边的范围必有峰值判断中间索引数和中间索引数的后一个数如果中间索引数小于中间索引数的后一个数那么中间索引右边的范围必有峰值如果上述bc都不成立那么中间索引数为峰值
实现代码
public int findPeakPoint(int[] arr) {int n arr.length;if (arr null || arr.length 0) {return -1;}if (arr.length 1) {return 0;}if (arr[0] arr[1]) {return 0;}if (arr[n - 1] arr[n - 2]) {return n - 1;}int left 1;int right n - 2;int ans -1;while (left right) {int mid left (right - left) / 2;if (arr[mid - 1] arr[mid]) {right mid - 1;} else if (arr[mid] arr[mid 1]) {left mid 1;} else {ans mid;break;}}return ans;}
