二分法查找（非递归）

二分查找法是查找算法里面，经典又比较简单的一种。它适用于从有序的数列中进行查找(比如数字和字母等)，将数列排序后再查找。

二分查找法的运行时间为对数时间O(㏒₂n)，即查找到需要的目标位置最多只需要㏒₂n 步。假设从[0, 99]的队列(100 个数，即 n=100)中寻到目标数 30，则需要查找步数为㏒₂100 , 即最多需要查找 7 次( 26 < 100 < 27)。
因为比较简单，话不多说直接撸代码
现有一组有序集合：[1, 3, 8, 10, 11, 67, 100]。要求写出通过二分法（非递归）查找 67 的完整代码

 * @description:
 * @date: 2021/11/22 22:13
 */
public class AlgorithmUtils {
    public static void main(String[] args) {
        int[] array = new int[]{1, 3, 8, 10, 11, 67, 100};
        int target = 67;
        System.out.println(AlgorithmUtils.binarySearch(array, target)); // 5
    }

    /**
     * 非递归二分法查找
     * @param array 待查找的数组(升序)
     * @param target 目标值
     * @return 目标值下标，找不到则返回-1
     */
    public static int binarySearch(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;
        while (left <= right) {
            int middle = (left + right) / 2;
            if (target == array[middle]) {
                return middle;
            } else if (target > array[middle]) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        return -1;
    }
}