二分查找算法(非递归)

基本介绍

  1. 我们之前学过二分查找算法，是使用递归的方式，这里主要讲二分查找算法的非递归方式；
  2. 二分查找法只适用于从有序的数列中进行查找(比如数组和字母)，将数列排序后再进行查找；
  3. 二分查找法的时间复杂度为O(log2_2n)，即查找到需要的目标位置最多只需要log2_2n步，假设从[0,99]的队列(100个数)中寻找目标数30，则需要查找步骤为log$_2$100，即最多需要查找7次(2^6<100<2^7)；

代码实现

数组{1,3,8,10,11,67,100}，编程实现二分查找，要求使用非递归的方式完成。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
package com.algorithm.binarySearchNoRecursion;

/**
 * @author Joker大雄
 * @data 2022/11/24 - 9:35
 **/
public class BinarySearchNoRe {
    public static void main(String[] args) {
        int[] arr = {1,3,8,10,11,67,100};
        // 测试二分查找
        int index = binarySearch(arr, 10);
        if(index!=-1){
            System.out.println("要查找的数的下标为："+index);
        }else{
            System.out.println("要查找的数不在该数组内");
        }
    }
    // 二分查找算法的非递归实现
    /**
     *
     * @param arr 待查找的数组，这里arr数组升序排列
     * @param target 需要查找的数
     * @return 返回对应的下标，-1表示没找到
     */
    public static int binarySearch(int[] arr,int target){
        int left = 0;
        int right = arr.length-1;
        while(left<=right){// 说明继续查找
            int mid = (left+right)/2;
            if(arr[mid] == target){
                return mid;
            }else if(arr[mid]>target){
                right = mid-1; //需要向左查找
            }else{
                left = mid +1; //需要向右边查找
            }
        }
        return -1; // 没找到
    }
}

运行结果

1
2
3
要查找的数的下标为：3

Process finished with exit code 0

分治算法的设计模式

基本介绍

  1. 分治算法是很重要的算法，字面上解释为"分而治之"，就是把一个复杂的问题分成两个或多个相同亦或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单的直接求解，原问题的解即对子问题解的合并。该技巧是很多高效算法的基础，例如排序算法(快速排序，归并排序)，傅里叶变换等。

  2. 分治算法求解的一些经典问题：

    • 汉诺塔

    • 二分搜索

    • 大整数乘法

    • 快速排序

    • 归并排序

    • 循环赛日程表

    • 线性时间选择

    • 最接近点对问题

基本步骤

分治算法再每一层递归上都有三个步骤：

  1. 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
  2. 解决：若子问题规模较小且容易求解，那么直接求解，否则递归的解各个子问题；
  3. 合并：将各个子问题的解合并为原问题的解；

设计模式

分治(Divide-and-Conquer§)算法设计模式如下：

1
2
3
4
5
6
7
if |P|<=n0
    then return(ADHOC(P))
// 将P分解为较小的子问题P1,P2,...,Pk
for i <- 1 to k
do yi <- Divide-and-Conquer(Pi) 递归解决Pi
T <- MERGE(y1,y2,....,yk) 合并子问题
return(T)

其中|P|表示问题P的规模：n0为一阈值，表示当问题P的规模不超过n0时，问题容易解决，不必再继续分解。

ADHOC§是该分治算法中的基本子算法，用于直接解决小规模的问题P；因此，当P的规模不超过n0时，直接用算法ADHOC§求解。

MERGE(y1,…,yk)是该分治算法中的合并子算法，用于将P的子问题P1,P2,…,PK的响应的解y1,y2,…,yk合并为P的解。

分治算法解决汉诺塔问题

汉诺塔问题

假设1s移动一次，移完这64个盘需要5845.54亿年以上；

汉诺塔问题源自印度一个古老的传说，印度教的 “创造之神” 梵天创造世界时做了 3 根金刚石柱，其中的一根柱子上按照从小到大的顺序摞着 64 个黄金圆盘。梵天命令一个叫婆罗门的门徒将所有的圆盘移动到另一个柱子上，移动过程中必须遵守以下规则：

  • 每次只能移动柱子最顶端的一个圆盘；
  • 每个柱子上，小圆盘永远要位于大圆盘之上；

思路分析

假设上方三个柱子从左到右分别为A,B,C，盘的个数为n；

  1. 如果n=1，移动：A->C。
  2. 如果有n>=2，可以总可以看作是两个部分，最下面的盘和最下面的盘向上的所有盘。移动：
    • 先把最上面的盘A->B；
    • 把最下面的盘A->C，移动过程使用到C塔；
    • 把B塔的所有盘从B->C，移动过程使用到A塔；

代码实现

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package com.algorithm.divideAndConquer;

/**
 * @author Joker大雄
 * @data 2022/11/24 - 10:58
 **/
public class HanoiTower {
    public static void main(String[] args) {
        System.out.println("汉诺塔3个盘移动步骤：");
        hanoiTower(3,'A','B','C');
    }

    // 汉诺塔移动方法(分治算法)
    public static void hanoiTower(int n,char A,char B,char C){
        // 如果只有一个盘，直接从A移动到C
        if(n==1){
            System.out.println("第"+n+"个盘从"+A+"->"+C);
        }else if(n>1){
            // 如果有n>=2，可以总可以看作是两个部分：
            // 最下面的盘 和 最下面的盘向上的所有盘
            // 先把最上面的盘A->B；移动过程使用到C塔
            hanoiTower(n-1,A,C,B);
            // 把最下面的盘A->C；
            System.out.println("第"+n+"个盘从"+A+"->"+C);
            // 把B塔的所有盘从B->C；移动过程使用到A塔
            hanoiTower(n-1,B,A,C);

        }else{
            System.out.println("汉诺塔盘为空");
        }
    }
}

运行结果

1
2
3
4
5
6
7
8
9
10
汉诺塔3个盘移动步骤：
第1个盘从A->C
第2个盘从A->B
第1个盘从C->B
第3个盘从A->C
第1个盘从B->A
第2个盘从B->C
第1个盘从A->C

Process finished with exit code 0