欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

二分查找的变体问题

程序员文章站 2022-07-05 16:02:34
之前一篇随笔介绍了二分查找的最最基本的实现,该实现要求待查找的数据是有序且不存在重复元素的数组。 而今天我们就要介绍二分查找的变体问题,待查找数据是有序但是存在重复元素的数组,主要有以下几个问题: 这个呢,就要比不存在重复元素的数组稍微复杂一些,但也不难,只要我们能够找好临界条件就事半功倍了。 原理 ......

之前一篇随笔介绍了二分查找的最最基本的实现,该实现要求待查找的数据是有序且不存在重复元素的数组。

而今天我们就要介绍二分查找的变体问题,待查找数据是有序但是存在重复元素的数组,主要有以下几个问题:

  1. 查找第一个等于指定值的元素的位置。
  2. 查找最后一个等于指定值的元素的位置。
  3. 查找第一个大于指定值的元素的位置。
  4. 查找最后一个小于指定值的元素的位置。

这个呢,就要比不存在重复元素的数组稍微复杂一些,但也不难,只要我们能够找好临界条件就事半功倍了。

原理呢,没有啥要讲的,可以直接看代码,很容易看懂,并且我同时写了通过递归实现和循环实现。

 

查找第一个等于指定值的元素的位置(第一种实现方式,该方式是找到了一个值之后,从该位置往前数看还有没有等于指定值的元素)

 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 }

 

  以上就是关于二分查找的几个变体问题了,代码还是比较详细的。