二分法

看下百度怎么说的

两个重点：1，有序2.时间复杂度0（log2n）：
推算如下假设某个数查找最坏的情况是最后一次才找到，
那么二分法每次都查找的范围为原来的1/2，假设总时间需要x,数据长度是N
那么总共需要：N*（1/2)~x=1=====>>x=logN  （次）
对于log2n不知道怎么处理的，对数函数知道吧，比如你找得数是8，以二为底数n，求结果为3，最坏的详情下三次能找到，8在最后一位。对数函数不知道，请自行学习，这里不再哔哔

时间复杂度只关系到最高次所以时间复杂度是：O（n^2）

package com.example.demo.util;

import com.alibaba.fastjson.JSON;
import lombok.Data;

import java.io.Serializable;
@Data
public class BinarySearch implements Serializable {
    //查找结果
    private int result;
    //查找结果所在位置
    private int index;
    //查询次数
    private  int count;
    //折中常量
    private final static int CONSTANT =2;

    /**
     *
     * @param arr 有序数组
     * @param tobeQueried  待查询数值
     * @param from  查询起始下标0
     * @param end   数值尺寸arr.length-1
     * @return
     */
    public  BinarySearch numberOfQuery(int [] arr,int tobeQueried,int from,int end) {
        ++count;
        BinarySearch binarySearch=new BinarySearch();
        int length = arr.length;
        if(length<=0||from<0||end>=length){
            binarySearch.setIndex(-1);
            binarySearch.setResult(tobeQueried);
            binarySearch.setCount(0);
            return binarySearch;
        }
        int temp = from + end;
        int mid = temp / CONSTANT;
        if(arr[mid]==tobeQueried){
            binarySearch.setIndex(mid);
            binarySearch.setResult(arr[mid]);
            binarySearch.setCount(count);
            return binarySearch;
        } else if(arr[mid]>tobeQueried){
            end= --mid;
            return numberOfQuery(arr,tobeQueried,from,end);
        }else if(arr[mid]            from= ++mid;
            return numberOfQuery(arr,tobeQueried,from,end);
        }
        return binarySearch;
    }

    public static void main(String[] args) {
        BinarySearch binarySearch=new BinarySearch();
        int a[]=new int[1000];
        for (int i=0;i<1000;i++){
            a[i]=i;
        }
        BinarySearch binarySearch1 = binarySearch.numberOfQuery(a, 999, 0, 999);
        System.out.println(JSON.toJSON(binarySearch1));
    }
}