之前一篇随笔介绍了二分查找的最最基本的实现，该实现要求待查找的数据是有序且不存在重复元素的数组。
而今天我们就要介绍二分查找的变体问题，待查找数据是有序但是存在重复元素的数组，主要有以下几个问题：
这个呢，就要比不存在重复元素的数组稍微复杂一些，但也不难，只要我们能够找好临界条件就事半功倍了。
原理呢，没有啥要讲的，可以直接看代码，很容易看懂，并且我同时写了通过递归实现和循环实现。
查找第一个等于指定值的元素的位置（第一种实现方式，该方式是找到了一个值之后，从该位置往前数看还有没有等于指定值的元素）
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: xingrui19 * @Description: 二分查找法（针对有序数组且存在重复元素（找到第一个指定值的位置）-递归方式实现）20 * @Date: 21:37 2019/2/1521 */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 else33 return binarySearch(nums, p, mid - 1, k);34 }35 36 /**37 * @Author: xingrui38 * @Description: 二分查找法（针对有序数组且不存在重复元素（找到第一个指定值的位置）-循环实现）39 * @Date: 21:37 2019/2/1540 */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 else53 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: xingrui19 * @Description: 二分查找法（针对有序数组且存在重复元素（找到第一个指定值的位置）-递归方式实现）20 * @Date: 21:37 2019/2/1521 */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 else34 return binarySearch(nums, p, mid - 1, k);35 }36 37 /**38 * @Author: xingrui39 * @Description: 二分查找法（针对有序数组且不存在重复元素（找到第一个指定值的位置）-循环实现）40 * @Date: 21:37 2019/2/1541 */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 else56 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: xingrui19 * @Description: 二分查找法（针对有序数组且存在重复元素（找到第一个指定值的位置）-递归方式实现）20 * @Date: 21:37 2019/2/1521 */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 else33 return binarySearch(nums, p, mid - 1, k);34 }35 36 /**37 * @Author: xingrui38 * @Description: 二分查找法（针对有序数组且不存在重复元素（找到第一个指定值的位置）-循环实现）39 * @Date: 21:37 2019/2/1540 */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 else53 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: xingrui19 * @Description: 二分查找法（针对有序数组且存在重复元素（找到第一个指定值的位置）-递归方式实现）20 * @Date: 21:37 2019/2/1521 */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 else34 return binarySearch(nums, mid 1, r, k);35 }36 37 /**38 * @Author: xingrui39 * @Description: 二分查找法（针对有序数组且不存在重复元素（找到第一个指定值的位置）-循环实现）40 * @Date: 21:37 2019/2/1541 */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 else56 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: xingrui19 * @Description: 二分查找法（针对有序数组且存在重复元素（找到第一个大于指定值的位置）-递归方式实现）20 * @Date: 21:37 2019/2/1521 */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: xingrui38 * @Description: 二分查找法（针对有序数组且不存在重复元素（找到第一个大于指定值的位置）-循环实现）39 * @Date: 21:37 2019/2/1540 */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 else54 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: xingrui19 * @Description: 二分查找法（针对有序数组且存在重复元素（找到第一个大于指定值的位置）-递归方式实现）20 * @Date: 21:37 2019/2/1521 */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 else34 return binarySearch(nums, mid 1, r, k);35 }36 }37 38 /**39 * @Author: xingrui40 * @Description: 二分查找法（针对有序数组且不存在重复元素（找到第一个大于指定值的位置）-循环实现）41 * @Date: 21:37 2019/2/1542 */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 else56 p = mid 1;57 }58 }59 return -1;60 }61 62 }
以上就是关于二分查找的几个变体问题了，代码还是比较详细的。
来源：http://www.icode9.com/content-4-118351.html
联系客服
