1、二分查找算法

二分查找(Binary Search)也叫作折半查找。二分查找有两个要求,一个是数列有序,另一个是数列使用顺序存储结构(比如数组)。

2、二分查找算法的思路分析

这里以数组[1,8,10,89,1000,1234]为例

  • 首先确定该数组中间元素的下标mid

mid = [left+right] / 2

  • 让需要查找的数findVal和arr[mid]比较,此时会出现以下几种情况
    • findVal>arr[mid],说明要查找的数在mid的右边,因此我们需要递归向右查找
    • findVal<arr[mid],说明要查找的数在mid的左边,因此我们需要递归向左查找
    • findVal=arr[mid],说明arr[mid]就是我们要寻找的值,直接返回mid
  • 结束递归的条件有
    • 找到目标值结束递归。
    • 递归完整个数组仍然没有找到findVal,也需要结束递归。即当left>right时结束递归。

3、递归二分查找算法的代码实现

递归退出条件1:寻找到目标值,此时返回mid

递归退出条件2:递归完整个数组没有找到目标值,此时left > right,返回-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
/***
* 二分查找算法
* @param arr 要查找的目标数组
* @param left 本次查找的左边界
* @param right 本次查找的右边界
* @param findVal 要查找的值
* @return findVal在arr中的下标,如果找不到返回-1
*/
public static int binarySearch(int[] arr,int left,int right,int findVal) {
if(left > right) {
//如果发现left值大于right值,那么证明此时数组已经递归完毕且数组中没有要寻找的值
//此时需要返回-1
return -1;
}
int mid = (left + right) / 2;
int midVal = arr[mid];
//如果要寻找的值小于当前的midVal
if(findVal > midVal) {
//向右递归
return binarySearch(arr,mid + 1,right,findVal);
} else if(findVal < midVal) {
//向左递归
return binarySearch(arr,left,mid - 1,findVal);
} else {
return mid;
}
}

4、测试

测试找不到的情况

1
2
3
4
5
public static void main(String[] args) {
int[] arr = {1,8,10,89,1000,1234};
int resultIndex = binarySearch(arr,0, arr.length - 1,10000);
System.out.println(resultIndex);
}

image-20210212170116299

测试找得到的情况

1
2
3
4
5
public static void main(String[] args) {
int[] arr = {1,8,10,89,1000,1234};
int resultIndex = binarySearch(arr,0, arr.length - 1,8);
System.out.println("resultIndex:" + resultIndex);
}

image-20210212170225794

5、改进二分查找算法

在一个数组中,如果有多个值与findVal值相同时,要求将这些值的下标都找到

思路分析如下:

  • 在找到mid索引值时,不要马上返回

  • 向mid索引值的左边扫描,将所有等于findVal的元素下标进入到一个集合中

  • 向mid索引值的右边扫描,将所有等于findVal的元素下标进入到一个集合中

  • 返回下标集合

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
/***
* 二分查找算法
* @param arr 要查找的目标数组
* @param left 本次查找的左边界
* @param right 本次查找的右边界
* @param findVal 要查找的值
* @return findVal在arr中的下标,如果找不到返回-1
*/
public static List<Integer> binarySearchAllElements(int[] arr,int left,int right,int findVal) {
if(left > right) {
//如果发现left值大于right值,那么证明此时数组已经递归完毕且数组中没有要寻找的值
//此时需要返回null
return null;
}
int mid = (left + right) / 2;
int midVal = arr[mid];
//如果要寻找的值小于当前的midVal
if(findVal > midVal) {
//向右递归
return binarySearchAllElements(arr,mid + 1,right,findVal);
} else if(findVal < midVal) {
//向左递归
return binarySearchAllElements(arr,left,mid - 1,findVal);
} else {
List<Integer> resIndexList = new ArrayList<>();
//实现向左边扫描
int temp = mid - 1;
while(true) {
//如果数组下标越界或者左边已经没有与findVal相等的值
if(temp < 0 || arr[temp] != findVal) {
//退出
break;
}
resIndexList.add(temp);
temp -= 1;
}
//将mid加入到集合中
resIndexList.add(mid);
//向右边扫描
temp = mid + 1;
while (true) {
if(temp > arr.length - 1 || arr[temp] != findVal) {
//退出
break;
}
resIndexList.add(temp);
temp += 1;
}
return resIndexList;
}
}

测试

1
2
3
4
5
public static void main(String[] args) {
int[] arr = {1,5,1000,1000,1000,1234,1999};
List<Integer> result = binarySearchAllElements(arr,0, arr.length - 1,1000);
System.out.println("结果下标为:" + result);
}

image-20210212171648097

6、非递归实现二分查找算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int binarySearch(int[] arr,int findVal) {
//如果数组为空直接return -1
if(arr == null) {
return -1;
}
int left = 0;
int right = arr.length - 1;
//在left小于right的情况下进行循环
while(left <= right) {
int mid = (left + right) / 2;
if(findVal < arr[mid]) {
//说明此时需要向左进行查找
right = mid - 1;
} else if(findVal > arr[mid]) {
//说明此时需要向右进行查找
left = mid + 1;
} else {
return mid;
}
}
//如果上面没有返回,证明数组中没有findVal,直接返回-1
return -1;
}

测试:

1
2
3
4
5
public static void main(String[] args) {
int[] arr = {1,5,888,1000,1111,1234,1999};
int resIndex = binarySearch(arr,5);
System.out.println("resIndex的值为:" + resIndex);
}

image-20210212172431234