【经典算法】二分查找法

二分查找法

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

而对称轴就是二分法中的中指针,根据目标值大小判断在中指针(对称轴)的左边还是右边,然后移动左指针 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