【经典算法】二分查找法

二分查找法

二分查找法是经典算法之一，二分查找我们在高中有接触过，在高中学习的抛物线中，有对称轴这一概念，在做题时我们经常会以对称轴来分类讨论。

而对称轴就是二分法中的中指针，根据目标值大小判断在中指针（对称轴）的左边还是右边，然后移动左指针 OR 右指针到中指针的位置，缩小搜索范围，缩小范围后再次判断目标值在中指针的左边还是右边，直到目标值位于左指针或者右指针的位置，找到目标值的下标。

代码实现

代码实现一

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
/**
 * 二分法基础
 * @param a             查找数组
 * @param target        查找目标值
 * @return              返回目标下标 or -1
 * 思路： 创建两个指针，分别指向数组两端，再使用一个中指针，
 * 用于判断目标值在中值的左侧还是右侧，然后再缩小范围，以此类推，可以缩小范围知道中值等于目标值
 */
static int binarySearch(int [] a,int target){
    // 定义左指针
    int i = 0;
    // 定义右指针
    int j = a.length-1;
    // 对左右指针的中值进行循环判断
    while (i<=j){
        // 取左右指针的中值， 向右移一位，或者除2
        int m = (i+j)>>>1;
        // 若中值小于目标值，说明值在中值右边
        if (a[m] < target){
            // 则将左指针移动到中值+1
            i = m+1;
            // 若中值大于目标值，说明目标值在中值左边
        } else if (a[m] > target) {
            // 则将右指针移动到中值-1
            j = m-1;
            // 当中值既不大于也不小于目标值，说明中值就是目标值
        } else {
            // 直接返回中值下标即可
            return m;
        }
    }
    return -1;
}

代码实现二

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
/**
 * 二分法改进版
 * @param a             查找数组
 * @param target        查找目标值
 * @return              返回数组下标 or -1
 * 思路： 创建两个指针，左右指针，右指针会溢出数组多一格
 * 右指针主要是为了区分边界值，右指针不会等于目标值，而左指针可能会等于目标值
 *
 */
static int basisSearch(int [] a, int target){
    // 定义左指针
    int i = 0 ;
    // 定义右指针，右指针会比数组长度多一格
    int j = a.length;
    // 循环遍历数组内，但左指针不等于右指针，因为右指针始终不会等于目标值，只当做边界值
    while (i<j){
        // 定义中值(中指针)
        int m = (i+j)>>>1;
        // 如果中指针小于目标值，则说明值在中指针右边，则将左指针移动到中值+1
        if (a[m]<target){
            i = m+1;
            // 如果中指针大于目标值，说明目标值在中指针坐标
        } else if (a[m] > target) {
            j=m;
        }else {
            return m;
        }
    }
    return -1;
}

代码实现三

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * 线性查找(暴力查找)
 * @param a             待查找的数组
 * @param target        待查找目标值
 * @return              返回数组下标 or -1
 */
static int linerSearch(int [] a,int target){
    for (int i = 0; i < a.length; i++) {
        if (a[i]==target){
            return i;
        }
    }
    return -1;
}

代码实现-测试

1
2
3
4
5
6
7
8
9
10
11
12
public static void main(String[] args) {
    int [] a ={13,15,19,22,65};
    int target = 22;

    // 二分查找法 基础版
    int i = binarySearch(a, target);
    // 二分查找法 改进版
    int i1 = basisSearch(a, target);
    // 线性查找
    int i2 = linerSearch(a, target);
    System.out.println(i2);
}

本文章来源于我的博客：https://blog.hikki.site