二分查找算法（非递归）

介绍

前面讲过 二分查找算法（递归），这里使用非递归形式实现。

二分查找法只适用于从 有序 的数列中查找（比如数字和字母等），将数列 **排序后 **再进行查找。

二分查找法的运行时间为对数时间 O(log₂n) ，即查找到目标位置最多只需要 log₂n 步，假设从 0~99 的队列（100 个数，即 n = 100），中旬到目标数 30，则需要查找的步数为 log₂100，即最多需要查找 7 次（2⁶ < 100 < 2⁷，100 介于 2 的 6、7 次方之间，次方则是寻找的步数）

代码实现

package cn.mrcode.study.dsalgtutorialdemo.algorithm.binarysearchnorecursion;

import org.junit.Test;

/**
 * 二分查找：非递归
 */
public class BinarySearchNoRecur {
    @Test
    public void fun() {
        int[] arr = new int[]{1, 3, 8, 10, 11, 67, 100};
        int target = 1;
        int result = binarySearch(arr, target);
        System.out.printf("查找 %d ,找位置为 %d \n", target, result);

        target = 11;
        result = binarySearch(arr, target);
        System.out.printf("查找 %d ,找位置为 %d \n", target, result);

        target = 100;
        result = binarySearch(arr, target);
        System.out.printf("查找 %d ,找位置为 %d \n", target, result);

        target = -1;
        result = binarySearch(arr, target);
        System.out.printf("查找 %d ,找位置为 %d \n", target, result);

        target = 200;
        result = binarySearch(arr, target);
        System.out.printf("查找 %d ,找位置为 %d \n", target, result);
    }

    /**
     * 二分查找：非递归
     *
     * @param arr 数组，前提：升序排列
     * @return 找到则返回下标，找不到则返回 -1
     */
    public int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length;
        int mid = 0;
        // 表示还可以进行查找
        while (left <= right) {
            mid = (left + right) / 2;
            if (mid >= arr.length // 查找的值大于数组中的最大值
            ) {
                // 防止越界
                return -1;
            }
            if (arr[mid] == target) {
                return mid;
            }
            // 升序：目标值比中间值大，则向左查找
            if (target > arr[mid]) {
                left = mid + 1;
            } else {
                // 否则：向右查找
                right = mid - 1;
            }
        }
        return -1;
    }
}

测试输出

查找 1 ,找位置为 0 
查找 11 ,找位置为 4 
查找 100 ,找位置为 6 
查找 -1 ,找位置为 -1 
查找 200 ,找位置为 -1