0%

二分法

原理

二分法查找,也称为折半法,是一种在有序数组中查找特定元素的搜索算法。

二分法查找的思路如下

1:首先,从数组的中间元素开始搜索,如果该元素正好是目标元素,则搜索过程结束,否则执行下一步。

2:如果目标元素大于/小于中间元素,则在数组大于/小于中间元素的那一半区域查找,然后重复步骤1的操作。

3:如果某一步数组为空,则表示找不到目标元素。

代码实现

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
package cn.joinhealth;

/**
* 二分法
*
* @author linjian
* @date 2022/7/14 09:43
*/
public class BisectionMethod {

public static void main(String[] args) {
int[] array = {1, 3, 5, 6};
System.out.println("binarySearch: " + binarySearch(array, 5) + "\n");
System.out.println("binarySearch2: " + binarySearch2(array, 5) + "\n");
System.out.println("binarySearch3: " + binarySearch3(array, 5, 0, 3) + "\n");
}

/**
* 左闭右闭的区间写法[left,right]: while(left<=right) left的改变为left=mid+1,right的改变为right=mid-1;
*
* @param nums 排序数组
* @param target 目标值
* @return
*/
public static int binarySearch(int[] nums, int target) {
int len = nums.length;
int left = 0, right = len - 1;
while (left <= right) {
int mid = (left + right) / 2;
System.out.println("searchInsert left: " + left + ",right: " + right + ",mid: " + mid + ",nums[mid]: " + nums[mid]);
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return right;
}

/**
* 左闭右开的区间写法[left,right) : while(left<right) left的改变为left=mid+1,right的改变为right=mid;
*
* @param nums 排序数组
* @param target 目标值
* @return
*/
public static int binarySearch2(int[] nums, int target) {
int len = nums.length;
//左闭右开所以right为len
int left = 0, right = len;
while (left < right) {
int mid = (left + right) / 2;
System.out.println("searchInsert2 left: " + left + ",right: " + right + ",mid: " + mid + ",nums[mid]: " + nums[mid]);
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return right;
}

/**
* 递归
*
* @param nums 排序数组
* @param target 目标值
* @param left 左角标
* @param right 右角标
* @return
*/
public static int binarySearch3(int[] nums, int target, int left, int right) {
if (left > right) {
return -1;
}
int mid = (left + right) / 2;
System.out.println("searchInsert3 left: " + left + ",right: " + right + ",mid: " + mid + ",nums[mid]: " + nums[mid]);
if (nums[mid] == target) {
return mid;
} else if (target < nums[mid]) {
return binarySearch3(nums, target, left, mid - 1);
} else {
return binarySearch3(nums, target, mid + 1, right);
}
}
}

结果输出

1
2
3
4
5
6
7
8
9
10
11
12
searchInsert left: 0,right: 3,mid: 1,nums[mid]: 3
searchInsert left: 2,right: 3,mid: 2,nums[mid]: 5
searchInsert left: 3,right: 3,mid: 3,nums[mid]: 6
binarySearch: 2

searchInsert2 left: 0,right: 4,mid: 2,nums[mid]: 5
searchInsert2 left: 0,right: 2,mid: 1,nums[mid]: 3
binarySearch2: 2

searchInsert3 left: 0,right: 3,mid: 1,nums[mid]: 3
searchInsert3 left: 2,right: 3,mid: 2,nums[mid]: 5
binarySearch3: 2