算法学习之二分法

二分查找法：

二分查找的核心一是输入为有序数组，只有当输入时有序数组时，二分查找才管用；而是核心算法就是从数组的中间开始查找，定义数组的low和high，分别是0和数组的长度减一，然后从中间开始比较，如果大了，则更新high，小了话则更新low，这样的话每次都能去除掉一半的数。二分查找的运行时间为，也就是2的对数，比如8个数，3次就可以找到，16个数，4次就可以找到，当数越大时，节约的时间越多。

题目：

输入一行有序数组，和一个目标数字，使用二分法查找有序数组中是否存在该目标数字，存在时输出查找次数和序号，如果找不到则输出查找次数以及未找到对应的数

package com.dlh.test;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class 二分法 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] string = sc.nextLine().split(" ");
        int item = sc.nextInt();
        int low = 0;
        int high = string.length - 1;
        int count = 0;
        boolean find = false;
        while (low <= high){
            int mid = (low + high)/2;
            int guess = Integer.parseInt(string[mid]);
            count++;
            if (guess == item){
                find = true;
                System.out.println("查找次数"+count+","+"找到序号"+ mid);
                break;
            }else if (guess > item){
                high = mid - 1;
            }else {
                low = mid + 1;
            }
        }
        if (!find){
            System.out.println("找了"+count+"次,"+"未找到对应的数");
        }
    }
}