第十四章：常用的十大算法

二分查找算法(非递归)介绍：
1、 二分查找法只适用于从有序的数列中进行查找(比如数字和字母等)，将数列排序后再进行查找
2、 二分查找法的运行时间为对数时间 O(㏒₂n) ，即查找到需要的目标位置最多只需要㏒₂n 步，假设从[0,99]的 队列(100 个数，即 n=100)中寻到目标数 30，则需要查找步数为㏒₂100 , 即最多需要查找 7 次(2^6 < 100 < 2^7)

package com.atguigu14.binarySearchNoRecur;

import java.util.Scanner;


public class BinarySearchNoRecur {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] array = {1, 3, 8, 10, 11, 67, 100};
        boolean loop = true;
        while (loop) {
            System.out.println("请输入你要查找的元素：");
            int value = scanner.nextInt();
            int result = binarySearch(array, value);
            if (result != -1) {
                System.out.println("要查找的元素的索引是： " + result);
            }
            System.out.println("退出请输入exit/否则输入任意字符继续：");
            String str = scanner.next();
            if (str.equals("exit")) {
                loop = false;
            }
        }
    }

    
    public static int binarySearch(int[] array, int target) {
        int left = 0;//左边界
        int right = array.length - 1;//右边界
        int mid;//中间的位置
        while (left <= right) {//如果满足左边界小于右边界的话，那么就可以继续循环下去
            mid = (right + left) / 2;//中间位置的坐标
            if (array[mid] == target) {
                //如果找到了对应的元素，那么就直接返回
                return mid;
            } else if (array[mid] > target) {
                //如果中间元素的位置比要查找的元素还要大，说明应该在中间元素的左边进行查找
                right = mid - 1;
            } else {
                //如果要查找的元素比中间元素还要大，说明应该在中间元素的右边寻找
                left = mid + 1;
            }
        }
        return -1;//如果没有找到，就返回一个-1
    }
}