二分查找法代码实现

1.概念

Alt text

  • 对于有序数列,才能使用二分查找法
  • 二分查找又称折半查找。
    • 优点:比较次数少、查找速度快、平均性能好
    • 缺点:要求待查表为有序表、插入和删除困难
    • 因此二分查找适用于不经常变动且查找频繁的有序列表

2.代码实现

  • 二分查找法:在有序数组 arr 中查找 target。
    • 如果找到 target,返回相应的索引 index。
    • 如果没有找到 target,返回 -1。
  • 时间复杂度:O(log n)
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/**
* @author: wjy
* @date: 2020/2/21
* @description: 二分查找法: 在有序数组arr中查找target。
* 如果找到target,返回相应的索引index。如果没有找到target,返回-1。
* 时间复杂度: O(log n)
*/
public class BinarySearch {

/**
* 功能描述: 使用迭代的方法实现二分查找法。
*
* @param: [arr, target]
* @return: int
* @auther: wjy
* @date: 2020/2/21 21:10
*/
public static int binarySearch(int[] arr, int target) {
// 在arr[l...r]之中查找target
int l = 0, r = arr.length - 1;
while (l <= r) {
// int mid = (l + r) / 2;
// 防止极端情况下的整形溢出,用以下方法求mid。
// int mid = l + (r - l) / 2;
// 模仿jdk源码中的写法,无符号右移一位。
int mid = (l + r) >>> 1;
if (arr[mid] == target) {
return mid;
}
else if (target < arr[mid]) {
// 在arr[l...mid-1]之中查找target
r = mid - 1;
}
else {
// 在arr[mid+1...r]之中查找target
l = mid + 1;
}
}
return -1;
}

/**
* 功能描述: 使用递归的方法实现二分查找法(性能上略差,但差异是常数级的)。
*
* @param: [arr, l, r, target]
* @return: int
* @auther: wjy
* @date: 2020/2/21 20:58
*/
public static int binarySearchByRecursion(int[] arr, int l, int r, int target) {
// 在arr[l...r]之中查找target
if (l > r) {
return -1;
}
// int mid = (l + r) / 2;
// 防止极端情况下的整形溢出,用以下方法求mid。
// int mid = l + (r - l) / 2, index = -1;
// 模仿jdk源码中的写法,无符号右移一位。
int mid = (l + r) >>> 1, index = -1;
if (arr[mid] == target) {
index = mid;
}
else if (target < arr[mid]) {
// 在arr[l...mid-1]之中查找target
index = binarySearchByRecursion(arr, l, mid - 1, target);
}
else {
// 在arr[mid+1...r]之中查找target
index = binarySearchByRecursion(arr, mid + 1, r, target);
}
return index;
}

/**
* 功能描述: 测试迭代方法和递归方法的正确性
*
* @param: [args]
* @return: void
* @auther: wjy
* @date: 2020/2/21 20:39
*/
public static void main(String[] args) {

// 生成一个有序数组
int n = 100;
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = i;
}
int random = (int) (Math.random() * n);
System.out.println("随机数: " + random + " 迭代方法执行结果: " + binarySearch(arr, random));
System.out.println("随机数: " + random + " 递归方法执行结果: " + binarySearchByRecursion(arr, 0, n - 1, random));
}
}

Alt text


3.Leetcode 题解举例


4.扩展问题

  • 如果有序数列中存在多个 target 值,我们应该返回什么呢?
  • 使用上述代码,并不能确定我们找到的索引具体对应哪一个 target。
  • 为了解决这个问题,我们额外定义两个函数:
    • ①floor() 函数: 返回 target 在数组中第一次出现的位置,若是元素不存在,返回数组中小于 target 的最大元素。
    • ②ceil() 函数: 返回 target 在数组中最后一次出现的位置,若是元素不存在,返回数组中大于 target 的最小元素。
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
* @author: wjy
* @date: 2020/2/21
* @description: 二分查找法的扩展问题: 当数组中存在多个target值时,应该返回什么?
*/
public class BinarySearchExtend {

public static int floor(int[] arr, int target) {
int l = 0, r = arr.length - 1;
while (l <= r) {
int mid = (l + r) >>> 1;
if (arr[mid] < target) {
l = mid + 1;
}
else {
r = mid - 1;
}
}
// 所有元素都小于target
if (l == arr.length) {
return l - 1;
}
return arr[l] == target? l: l - 1;
}

public static int ceil(int[] arr, int target) {
int l = 0, r = arr.length - 1;
while (l <= r) {
int mid = (l + r) >>> 1;
if (arr[mid] > target) {
r = mid - 1;
}
else {
l = mid + 1;
}
}
// 所有元素都大于target
if (r < 0) {
return 0;
}
// 所有元素都小于target
if (l == arr.length) {
return l - 1;
}
return arr[r] == target? r: r + 1;
}

/**
* 功能描述: 测试floor()函数和ceil()函数
*
* @param: [args]
* @return: void
* @auther: wjy
* @date: 2020/2/21 20:39
*/
public static void main(String[] args) {

int[] arr = {0, 1, 3, 4, 4, 4, 4, 5, 6, 6};
int random = (int) (Math.random() * arr.length);
System.out.println("floor(arr, " + random + ") = " + floor(arr, random));
System.out.println("ceil(arr, " + random + ") = " + ceil(arr, random));
}
}

Alt text


附录

0%