class006 二分搜索【算法】

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;
  }
}

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;
  }
}

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;
  }
}

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;
    }
  }
}