二分法查找(非递归)

简介: 二分查找法是查找算法里面,经典又比较简单的一种。它适用于从有序的数列中进行查找(比如数字和字母等),将数列排序后再查找。二分查找法的运行时间为对数时间O(㏒₂n),即查找到需要的目标位置最多只需要㏒₂n 步。假设从[0, 99]的队列(100 个数,即 n=100)中寻到目标数 30,则需要查找步数为㏒₂100 , 即最多需要查找 7 次( 26 < 100 < 27)。

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

二分查找法的运行时间为对数时间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;
    }
}
相关文章
|
23天前
|
算法
递归算法实现二分查找
本文简要介绍了递归实现的二分查找算法,这是一种在有序列表中快速查找的策略。递归方法虽在实际应用中较少,但有助于理解递归思想,为学习数据结构中的树内容打下基础。文中提供了原版和递归版本的二分查找代码,并强调了递归算法中处理未找到情况的注意事项。此外,还提到了递归在解决复杂问题时的优势,并通过链接分享了一个关于递归实现素数判断的例子。
31 2
|
1月前
|
存储 搜索推荐
【非递归版】快速排序算法(4)
【非递归版】快速排序算法(4)
23 0
顺序表应用7:最大子段和之分治递归法
顺序表应用7:最大子段和之分治递归法
|
11月前
二分法查找(折半查找)
二分法查找(折半查找)
42 0
|
12月前
非递归实现二叉树遍历
非递归实现二叉树遍历
37 0
|
搜索推荐 算法
归并排序(递归+非递归)
归并排序(递归+非递归)
|
Windows
归并排序 (递归+非递归)
归并排序 (递归+非递归)
71 0
|
算法
2-路归并排序的递归实现和非递归实现
2-路归并排序的递归实现和非递归实现
字符串逆序(递归和非递归实现)
给连两个指针,left放在字符串左侧,right放在最后一个有效字符位置。 交换两个指针位置上的字符

热门文章

最新文章