class006 二分搜索【算法】
code1 有序数组中是否存在一个数字
// 有序数组中是否存在一个数字
package class006; import java.util.Arrays; // 有序数组中是否存在一个数字 public class Code01_FindNumber { // 为了验证 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 (right(arr, num) != exist(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; } // 为了验证 // 保证arr有序,才能用这个方法 public static boolean right(int[] sortedArr, int num) { for (int cur : sortedArr) { if (cur == num) { return true; } } return false; } // 保证arr有序,才能用这个方法 public static boolean exist(int[] arr, int num) { if (arr == null || arr.length == 0) { return false; } int l = 0, r = arr.length - 1, m = 0; while (l <= r) { m = (l + r) / 2; if (arr[m] == num) { return true; } else if (arr[m] > num) { r = m - 1; } else { l = m + 1; } } return false; } }
code2 有序数组中找>=num的最左位置
// 有序数组中找>=num的最左位置
package class006; import java.util.Arrays; // 有序数组中找>=num的最左位置 public class Code02_FindLeft { // 为了验证 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() * N); if (right(arr, num) != findLeft(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; } // 为了验证 // 保证arr有序,才能用这个方法 public static int right(int[] arr, int num) { for (int i = 0; i < arr.length; i++) { if (arr[i] >= num) { return i; } } return -1; } // 保证arr有序,才能用这个方法 // 有序数组中找>=num的最左位置 public static int findLeft(int[] arr, int num) { int l = 0, r = arr.length - 1, m = 0; int ans = -1; while (l <= r) { // m = (l + r) / 2; // m = l + (r - l) / 2; m = l + ((r - l) >> 1); if (arr[m] >= num) { ans = m; r = m - 1; } else { l = m + 1; } } return ans; } }
code3 有序数组中找<=num的最右位置
// 有序数组中找<=num的最右位置
package class006; import java.util.Arrays; // 有序数组中找<=num的最右位置 public class Code03_FindRight { // 为了验证 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() * N); if (right(arr, num) != findRight(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; } // 为了验证 // 保证arr有序,才能用这个方法 public static int right(int[] arr, int num) { for (int i = arr.length - 1; i >= 0; i--) { if (arr[i] <= num) { return i; } } return -1; } // 保证arr有序,才能用这个方法 // 有序数组中找<=num的最右位置 public static int findRight(int[] arr, int num) { int l = 0, r = arr.length - 1, m = 0; int ans = -1; while (l <= r) { m = l + ((r - l) >> 1); if (arr[m] <= num) { ans = m; l = m + 1; } else { r = m - 1; } } return ans; } }
code4 162. 寻找峰值
// 峰值元素是指其值严格大于左右相邻值的元素
// 给你一个整数数组 nums,已知任何两个相邻的值都不相等
// 找到峰值元素并返回其索引
// 数组可能包含多个峰值,在这种情况下,返回 任何一个峰值 所在位置即可。
// 你可以假设 nums[-1] = nums[n] = 无穷小
// 你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
// 测试链接 : https://leetcode.cn/problems/find-peak-element/
package class006; // 峰值元素是指其值严格大于左右相邻值的元素 // 给你一个整数数组 nums,已知任何两个相邻的值都不相等 // 找到峰值元素并返回其索引 // 数组可能包含多个峰值,在这种情况下,返回 任何一个峰值 所在位置即可。 // 你可以假设 nums[-1] = nums[n] = 无穷小 // 你必须实现时间复杂度为 O(log n) 的算法来解决此问题。 public class Code04_FindPeakElement { // 测试链接 : https://leetcode.cn/problems/find-peak-element/ class Solution { 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; } } }
2023-12-10 13:12:08