用Java进行基础算法了解（一）二分查找

二分查找，是最基础的查询方式。它的思想是：面对顺序查询逻辑会有很长的线性时间，例如1-100，寻找76这个数，普通查询要遍历1-100，到76才确认，查询了76次，显而易见，我们从中间去寻找更符合人的思想，更符合理性思维。

面对一个有序的元素列表，我们查找列表里的元素位置：

package com.person.suanfa.text;

import java.util.Scanner;

public class Erfenfa {
    public static void main(String[] args) {
        int[] list = {1,2,3,4,5,6,7,8,9,10};
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入你想要查询的数字");
        int item = scanner.nextInt();
        int low = 0 ;
        int high = list.length-1 ;
        int mid = 0 ;
        int guess = 0 ;
        while(low <= high){
            mid = (low + high)/2;
            guess = list[mid];
            if(guess == item){
                System.out.println("数字的位置是:"+mid);
            }
            if(guess < item){
                low = mid+1;
            }
            else {
                high = mid-1;
            }
        }
    }
}

由此显而易见，我们查询一个有序包含n个元素的list，最多用log2 n 步，普通顺序查询要n步。

顺序查询，猜测次数与列表长度相同，称为线性时间。二分查找法，查询时间明显不同，运行时间叫做对数时间也叫作log时间。

大O表达式O(log n)表达是一种操作数（最糟糕情况下），不是时间，指出了算法的增速。

所以说，我们谈论算法，不能单纯谈论速度，是随着输入的增加，其运算时间随着什么样的速度增加。实际上，随着元素的增多，差异越来越大。

 当然也有很多大O表达式，例如：O(n *log n)     O（n*n） O（n！）

我们用画格子来简单体现一下时间，画一下时间0.1秒，体现一下最常见的五种运行时间。