68：查找插入位置

:::info 题目：输入一个排序的整数数组nums和一个目标值t，如果数组nums中包含t，则返回t在数组中的下标；如果数组nums中不包含t，则返回将t按顺序插入数组nums中的下标。假设数组中没有相同的数字。例如，输入数组nums为[1，3，6，8]，如果目标值t为3，则输出1；如果t为5，则返回2。 :::

public class SearchInsert {
    public static int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            // nums[mid]
            if (nums[mid] >= target) {
                if (mid == 0 || nums[mid - 1] < target) {
                    // 且nums[mid-1]小于target，那mid就是我们要找的
                    // 如果mid已经是0了，意味着所有的数字都大于等于target，那t就插入0的位置
                    return mid;
                }
                // 如果nums[mid-1]也是小于t，那就在mid -1 之前找
                right = mid - 1;
            } else {
                // 如果nums[mid]小于t，那么位置一定在mid的后面，left更新为 mid+1
                left = mid + 1;
            }
        }
        return nums.length;
    }
    public static void main(String[] args) {
        int[] arr = {1,2,3,5,6};
        System.out.println(searchInsert(arr, 4) == 3);
    }
}

69：山峰数组的顶部

:::info 题目：在一个长度大于或等于3的数组中，任意相邻的两个数字都不相等。该数组的前若干数字是递增的，之后的数字是递减的，因此它的值看起来像一座山峰。请找出山峰顶部，即数组中最大值的位置。例如，在数组[1，3，5，4，2]中，最大值是5，输出它在数组中的下标2。 :::

public class PeakIndexInMountainArray {
    public static int peakIndex(int[] arr) {
        int left = 0;
        int right = arr.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (mid == 0 || mid == arr.length - 1) {
                return  mid;
            }
            if (arr[mid - 1] < arr[mid] && arr[mid] > arr[mid + 1]) {
                return mid;
            }
            if (arr[mid] > arr[mid - 1]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return arr.length;
    }
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 2, 1};
        System.out.println(peakIndex(arr) == 2);
        int[] arr1 = {1, 2, 3};
        System.out.println(peakIndex(arr1) == 2);
        int[] arr2 = {3, 2, 1};
        System.out.println(peakIndex(arr2) == 0);
    }
}