网站域名301重定向,wordpress 视频站模版,福州seo排名外包,大连建设网站题目#xff1a; 1. 在有序数组中确定num存在还是不存在。 2. 在有序数组中找num的最左位置。 3. 在有序数组中找num的最右位置。 4. 二分搜索不一定发生在有序数组上#xff08;比如寻找峰值问题#xff09;。 5. 二分答案法。 题目一
简单的二分搜索法。
public… 题目 1. 在有序数组中确定num存在还是不存在。 2. 在有序数组中找num的最左位置。 3. 在有序数组中找num的最右位置。 4. 二分搜索不一定发生在有序数组上比如寻找峰值问题。 5. 二分答案法。 题目一
简单的二分搜索法。
public static boolean exist(int[] arr, int num) {if(arr null || arr.length 0) return false;int l 0, r arr.length - 1;while(l r) {int mid (l r) / 2;if(arr[mid] num) {return true;} else if (arr[mid] num) {l mid 1;} else {r mid - 1;}}return false;}
题目二
还是很简单。
public static int exist(int[] arr, int num) {if(arr null || arr.length 0) return -1;int l 0, r arr.length - 1;int res -1;while(l r) {
// int mid (l r) / 2; // 防止数组长度过长溢出int mid l ((r - l) 1);if(arr[mid] num) {res mid;r mid - 1;} else {l mid 1;}}return res;}
题目三
和上一题一致。
public static int exist(int[] arr, int num) {if(arr null || arr.length 0) return -1;int l 0, r arr.length - 1;int res -1;while(l r) {
// int mid (l r) / 2; // 防止数组长度过长溢出int mid l ((r - l) 1);if(arr[mid] num) {res mid;l mid 1;} else {r mid - 1;}}return res;}
题目四
题目中规定相邻两数不相等且默认超出界限的值为无穷小题目可能存在多个峰值只需返回一个即可。要注意的是如果0位置和size - 1位置不满足峰值也就是0处小于1处的值size - 1处小于size - 2处的值就意味着中间一定存在峰值也就是起始位置单调递增末尾位置单调递减故而中间也就是[1,size - 2]区间必然存在极值。于是可以再找中间的值来判定是否满足峰值如果它小于左边的值那就意味着峰值在左边区间如果大于右边的值就在右边的区间找如果是极小值只需要在两个区间中随便选一个找即可。依据这个原理可以不断缩小要判断的范围这也就是能使用二分法的原因。
public int findPeakElement(int[] arr) {if(arr null || arr.length 0) return -1;if(arr.length 1) return 0;int l 0, r arr.length - 1;if(arr[l] arr[l 1]) return l;l ;if(arr[r] arr[r - 1]) return r;r --;while(l r) {
// int mid (l r) / 2; // 防止数组长度过长溢出int mid l ((r - l) 1);if(arr[mid - 1] arr[mid]) {r mid - 1;} else if(arr[mid 1] arr[mid]) {l mid 1;} else {return mid;}}return -1;}
总结无论整体是否有序只要确定判定完中间值之后可以进而确定哪一侧必然存在要找的值或者某侧必然不存在要找的值也就是缩小一半的寻找范围就可以使用二分搜索法。
