二分查找的变体问题
程序员文章站
2022-04-09 18:52:56
之前一篇随笔介绍了二分查找的最最基本的实现，该实现要求待查找的数据是有序且不存在重复元素的数组。 而今天我们就要介绍二分查找的变体问题，待查找数据是有序但是存在重复元素的数组，主要有以下几个问题： 这个呢，就要比不存在重复元素的数组稍微复杂一些，但也不难，只要我们能够找好临界条件就事半功倍了。 原理 ......
之前一篇随笔介绍了二分查找的最最基本的实现，该实现要求待查找的数据是有序且不存在重复元素的数组。
而今天我们就要介绍二分查找的变体问题，待查找数据是有序但是存在重复元素的数组，主要有以下几个问题：
- 查找第一个等于指定值的元素的位置。
- 查找最后一个等于指定值的元素的位置。
- 查找第一个大于指定值的元素的位置。
- 查找最后一个小于指定值的元素的位置。
这个呢，就要比不存在重复元素的数组稍微复杂一些，但也不难，只要我们能够找好临界条件就事半功倍了。
原理呢，没有啥要讲的，可以直接看代码，很容易看懂，并且我同时写了通过递归实现和循环实现。
查找第一个等于指定值的元素的位置（第一种实现方式，该方式是找到了一个值之后，从该位置往前数看还有没有等于指定值的元素）
1 package com.structure.search;
2
3 /**
4 * 二分查找法
5 *
6 * @author zhangxingrui
7 * @create 2019-02-15 21:29
8 **/
9 public class binarysearch_firstvalue {
10
11 public static void main(string[] args) {
12 int[] nums = new int[]{4, 6, 9, 9, 19, 19, 30, 30, 40, 500, 500, 500004, 500004};
13 system.out.println(binarysearch(nums, 0, nums.length - 1, 30));
14 system.out.println(binarysearch(nums, 30));
15 }
16
17 /**
18 * @author: xingrui
19 * @description: 二分查找法（针对有序数组且存在重复元素（找到第一个指定值的位置）-递归方式实现）
20 * @date: 21:37 2019/2/15
21 */
22 private static int binarysearch(int[] nums, int p, int r, int k){
23 if(p > r)
24 return -1;
25
26 int mid = (p + r) / 2;
27 if(nums[mid] == k)
28 return getminindex(nums, mid, k);
29
30 if(k > nums[mid])
31 return binarysearch(nums, mid + 1, r, k);
32 else
33 return binarysearch(nums, p, mid - 1, k);
34 }
35
36 /**
37 * @author: xingrui
38 * @description: 二分查找法（针对有序数组且不存在重复元素（找到第一个指定值的位置）-循环实现）
39 * @date: 21:37 2019/2/15
40 */
41 private static int binarysearch(int[] nums, int k){
42 int p = 0;
43 int r = nums.length - 1;
44 while (p <= r){
45 int mid = (p + r) / 2;
46
47 if(nums[mid] == k)
48 return getminindex(nums, mid, k);
49
50 if(k > nums[mid])
51 p = mid + 1;
52 else
53 r = mid - 1;
54 }
55 return -1;
56 }
57
58 private static int getminindex(int[] numbers, int mid, int k){
59 while (mid > 0 && numbers[mid - 1] == k){
60 mid--;
61 }
62 return mid;
63 }
64
65 }
查找第一个等于指定值的元素的位置（第二种实现方式，该方式是找到了一个值之后，判断当前位置是否是临界元素，如果不是则继续执行）
1 package com.structure.search;
2
3 /**
4 * 二分查找法
5 *
6 * @author zhangxingrui
7 * @create 2019-02-15 21:29
8 **/
9 public class binarysearch_firstvalue2 {
10
11 public static void main(string[] args) {
12 int[] nums = new int[]{4, 6, 9, 9, 19, 19, 30, 30, 30, 30, 40};
13 system.out.println(binarysearch(nums, 0, nums.length - 1, 30));
14 system.out.println(binarysearch(nums, 30));
15 }
16
17 /**
18 * @author: xingrui
19 * @description: 二分查找法（针对有序数组且存在重复元素（找到第一个指定值的位置）-递归方式实现）
20 * @date: 21:37 2019/2/15
21 */
22 private static int binarysearch(int[] nums, int p, int r, int k){
23 if(p > r)
24 return -1;
25 int mid = (p + r) / 2;
26
27 if(k > nums[mid])
28 return binarysearch(nums, mid + 1, r, k);
29 else if(k < nums[mid])
30 return binarysearch(nums, p, mid - 1, k);
31 if(mid == 0 || nums[mid - 1] != k)
32 return mid;
33 else
34 return binarysearch(nums, p, mid - 1, k);
35 }
36
37 /**
38 * @author: xingrui
39 * @description: 二分查找法（针对有序数组且不存在重复元素（找到第一个指定值的位置）-循环实现）
40 * @date: 21:37 2019/2/15
41 */
42 private static int binarysearch(int[] nums, int k){
43 int p = 0;
44 int r = nums.length - 1;
45
46 while (p <= r){
47 int mid = (p + r) / 2;
48
49 if(k > nums[mid])
50 p = mid + 1;
51 else if(k < nums[mid])
52 r = mid - 1;
53 else if(mid == 0 || nums[mid - 1] != k)
54 return mid;
55 else
56 r = mid - 1;
57 }
58 return -1;
59 }
60
61 }
查找最后一个等于指定值的元素的位置（第一种实现方式，该方式是找到了一个值之后，从该位置往后数看还有没有等于指定值的元素）
1 package com.structure.search;
2
3 /**
4 * 二分查找法
5 *
6 * @author zhangxingrui
7 * @create 2019-02-15 21:29
8 **/
9 public class binarysearch_lastvalue {
10
11 public static void main(string[] args) {
12 int[] nums = new int[]{4, 6, 9, 9, 19, 19, 30, 30, 40, 500, 500, 500004, 500004};
13 system.out.println(binarysearch(nums, 0, nums.length - 1, 30));
14 system.out.println(binarysearch(nums, 30));
15 }
16
17 /**
18 * @author: xingrui
19 * @description: 二分查找法（针对有序数组且存在重复元素（找到第一个指定值的位置）-递归方式实现）
20 * @date: 21:37 2019/2/15
21 */
22 private static int binarysearch(int[] nums, int p, int r, int k){
23 if(p > r)
24 return -1;
25
26 int mid = (p + r) / 2;
27 if(nums[mid] == k)
28 return getmaxindex(nums, mid, k);
29
30 if(k > nums[mid])
31 return binarysearch(nums, mid + 1, r, k);
32 else
33 return binarysearch(nums, p, mid - 1, k);
34 }
35
36 /**
37 * @author: xingrui
38 * @description: 二分查找法（针对有序数组且不存在重复元素（找到第一个指定值的位置）-循环实现）
39 * @date: 21:37 2019/2/15
40 */
41 private static int binarysearch(int[] nums, int k){
42 int p = 0;
43 int r = nums.length - 1;
44 while (p <= r){
45 int mid = (p + r) / 2;
46
47 if(nums[mid] == k)
48 return getmaxindex(nums, mid, k);
49
50 if(k > nums[mid])
51 p = mid + 1;
52 else
53 r = mid - 1;
54 }
55 return -1;
56 }
57
58 private static int getmaxindex(int[] numbers, int mid, int k){
59 int length = numbers.length;
60 while (mid < length && numbers[mid + 1] == k){
61 mid++;
62 }
63 return mid;
64 }
65
66 }
查找最后一个等于指定值的元素的位置（第二种实现方式，该方式是找到了一个值之后，判断当前位置是否是临界元素，如果不是则继续执行）
1 package com.structure.search;
2
3 /**
4 * 二分查找法
5 *
6 * @author zhangxingrui
7 * @create 2019-02-15 21:29
8 **/
9 public class binarysearch_lastvalue2 {
10
11 public static void main(string[] args) {
12 int[] nums = new int[]{4, 6, 9, 9, 19, 19, 30, 30, 30, 30, 40};
13 system.out.println(binarysearch(nums, 0, nums.length - 1, 30));
14 system.out.println(binarysearch(nums, 30));
15 }
16
17 /**
18 * @author: xingrui
19 * @description: 二分查找法（针对有序数组且存在重复元素（找到第一个指定值的位置）-递归方式实现）
20 * @date: 21:37 2019/2/15
21 */
22 private static int binarysearch(int[] nums, int p, int r, int k){
23 if(p > r)
24 return -1;
25 int mid = (p + r) / 2;
26
27 if(k > nums[mid])
28 return binarysearch(nums, mid + 1, r, k);
29 else if(k < nums[mid])
30 return binarysearch(nums, p, mid - 1, k);
31 if(mid == nums.length - 1 || nums[mid + 1] != k)
32 return mid;
33 else
34 return binarysearch(nums, mid + 1, r, k);
35 }
36
37 /**
38 * @author: xingrui
39 * @description: 二分查找法（针对有序数组且不存在重复元素（找到第一个指定值的位置）-循环实现）
40 * @date: 21:37 2019/2/15
41 */
42 private static int binarysearch(int[] nums, int k){
43 int p = 0;
44 int r = nums.length - 1;
45
46 while (p <= r){
47 int mid = (p + r) / 2;
48
49 if(k > nums[mid])
50 p = mid + 1;
51 else if(k < nums[mid])
52 r = mid - 1;
53 else if(mid == nums.length - 1 || nums[mid + 1] != k)
54 return mid;
55 else
56 p = mid + 1;
57 }
58 return -1;
59 }
60
61 }
查找第一个大于指定值的元素的位置
1 package com.structure.search;
2
3 /**
4 * 二分查找法
5 *
6 * @author zhangxingrui
7 * @create 2019-02-15 21:29
8 **/
9 public class binarysearch_firstgreatervalue {
10
11 public static void main(string[] args) {
12 int[] nums = new int[]{4, 6, 9, 9, 19, 19, 30, 30, 30, 30, 40};
13 system.out.println(binarysearch(nums, 0, nums.length - 1, 9));
14 system.out.println(binarysearch(nums, 9));
15 }
16
17 /**
18 * @author: xingrui
19 * @description: 二分查找法（针对有序数组且存在重复元素（找到第一个大于指定值的位置）-递归方式实现）
20 * @date: 21:37 2019/2/15
21 */
22 private static int binarysearch(int[] nums, int p, int r, int k){
23 if(p > r)
24 return -1;
25 int mid = (p + r) / 2;
26
27 if(k >= nums[mid])
28 return binarysearch(nums, mid + 1, r, k);
29 else{
30 if(mid == nums.length - 1 || nums[mid - 1] <= k)
31 return mid;
32 else return binarysearch(nums, p, mid - 1, k);
33 }
34 }
35
36 /**
37 * @author: xingrui
38 * @description: 二分查找法（针对有序数组且不存在重复元素（找到第一个大于指定值的位置）-循环实现）
39 * @date: 21:37 2019/2/15
40 */
41 private static int binarysearch(int[] nums, int k){
42 int p = 0;
43 int r = nums.length - 1;
44
45 while (p <= r){
46 int mid = (p + r) / 2;
47
48 if(k >= nums[mid])
49 p = mid + 1;
50 else if(k < nums[mid]){
51 if(mid == nums.length - 1 || nums[mid - 1] == k)
52 return mid;
53 else
54 r = mid - 1;
55 }
56 }
57 return -1;
58 }
59
60 }
查找最后一个小于指定值的元素的位置
1 package com.structure.search;
2
3 /**
4 * 二分查找法
5 *
6 * @author zhangxingrui
7 * @create 2019-02-15 21:29
8 **/
9 public class binarysearch_lastlessvalue {
10
11 public static void main(string[] args) {
12 int[] nums = new int[]{4, 6, 9, 9, 19, 19, 30, 30, 30, 30, 40};
13 system.out.println(binarysearch(nums, 0, nums.length - 1, 30));
14 system.out.println(binarysearch(nums, 30));
15 }
16
17 /**
18 * @author: xingrui
19 * @description: 二分查找法（针对有序数组且存在重复元素（找到第一个大于指定值的位置）-递归方式实现）
20 * @date: 21:37 2019/2/15
21 */
22 private static int binarysearch(int[] nums, int p, int r, int k){
23 if(p > r)
24 return -1;
25 int mid = (p + r) / 2;
26
27 if(k <= nums[mid]){
28 return binarysearch(nums, p, mid - 1, k);
29 }
30 else{
31 if(mid == 0 || nums[mid + 1] == k)
32 return mid;
33 else
34 return binarysearch(nums, mid + 1, r, k);
35 }
36 }
37
38 /**
39 * @author: xingrui
40 * @description: 二分查找法（针对有序数组且不存在重复元素（找到第一个大于指定值的位置）-循环实现）
41 * @date: 21:37 2019/2/15
42 */
43 private static int binarysearch(int[] nums, int k){
44 int p = 0;
45 int r = nums.length - 1;
46
47 while (p <= r){
48 int mid = (p + r) / 2;
49
50 if(k <= nums[mid])
51 r = mid - 1;
52 else if(k > nums[mid]){
53 if(mid == 0 || nums[mid + 1] == k)
54 return mid;
55 else
56 p = mid + 1;
57 }
58 }
59 return -1;
60 }
61
62 }
以上就是关于二分查找的几个变体问题了，代码还是比较详细的。
上一篇： Python 之异常处理
下一篇： C语言数据结构基础学习笔记——栈和队列