二分法的三种应用

//    思路：使用二分法
package dichotomy;

import java.util.Scanner;


public class dichotomy_1 {
    public static void main(String[] args) {
        int[] arr = {1, 4, 8, 12, 20, 33, 57, 69, 99};
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入你想找的数: ");
        int num = sc.nextInt();
        boolean temp = search(arr, num);
        System.out.println(temp);

    }

    public static boolean search(int[] arr, int num) {
        boolean temp = false;
        int min = 0;
        int max = arr.length - 1;
        if (num > arr[max] || num < arr[min]) {
            temp = false;
        }
        while (min <= max) {
            int mid = (min + max) / 2;//mid=(min+max)/2
            if (arr[mid] == num) {
                temp = true;
                break;
            } else if (arr[mid] > num) {
                max = mid - 1;
            } else {
                min = mid + 1;
            }
        }
        return temp;


    }
}

//在一个有序数组中找到大于等于某个数最左侧的位置

package dichotomy;

import java.util.Scanner;

public class dichotomy_2 {
    public static void main(String[] args) {
        int[] arr={1,1,1,2,2,2,2,2,3,3,3,3,4,4,5,5,5,5,5,5,5,};
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入一个数: ");
        int num = sc.nextInt();
        int result = search(arr, num);
        System.out.println(result);

    }

    public static int search(int[] arr, int num) {
        int temp=-1 ;
        int min = 0;
        int max = arr.length - 1;
        if (num > arr[max] || num < arr[min]) {
            temp=-1;
        }
        while (min <= max) {
            int mid = (min + max) / 2;//mid=(min+max)/2
            if(arr[mid]>=num){
                if(mid==0||arr[mid-1] 
 
三、进阶二 
二分法不一定非要有序才能使用 !!! 
数组arr无序且相邻两个数不相同，求局部最小,要求时间复杂度好于O(n) 
/*
    数组arr无序且相邻两个数不相同，求局部最小,要求时间复杂度好于O(n)
    分析：arr[0]arr[i]且arr[i]arr[1]且arr[i-1]>arr[i-2]
        else{
            for(int i=1;i