Java二分法查找(递归、循环实现)
程序员文章站
2022-04-27 10:42:38
Java二分法查找(递归、循环实现)public class BinarySearch { public static void main(String[] args) { /** * @author JadeXu * @// TODO: 2020/12/7 二分查找 * 思路: * 1、获取数组的中间值,先获取下标,方便多次查找 * 奇数位的数组直接获取中间位,偶数位的数组获取中间的第一位或...
Java二分法查找(递归、循环实现)
public class BinarySearch {
public static void main(String[] args) {
/**
* @author JadeXu
* @// TODO: 2020/12/7 二分查找
* 思路:
* 1、获取数组的中间值,先获取下标,方便多次查找
* 奇数位的数组直接获取中间位,偶数位的数组获取中间的第一位或第二位都可,
* 一般获取第一位(因为与奇数位获取中间值的方法一样)
* 2、获取查找的区间范围,start:区间开始的下标,end:区间结束的下标
* 3、判断查找的数和中间位的数是否相同
* 相同时,直接返回需要的数据,跳出方法
* 大于时,即数可能在中间值右边的区间内,此时将开始下标+1,即往后移一位,
* 就得到了中间值右边区间的开始下标。
* 小于时,即数可能在中间值左边的区间内,此时将结束下标-1,即往前移一位,
* 就得到了中间值左边区间的结束下标。
* 当一个区间里,开始下标小于等于结束下标时,该区间才是有效区间,才能继续查找。
* 否则无效,返回找不到,跳出方法。
*/
}
/**
*循环
* @param arr 已经升序好的int[]
* @param num 需要查找的数字
* @return 找到则返回下标,没找到则返回-1
*/
private static int binarySearchByCycle(int[] arr,int num) {
int start = 0;
int end = arr.length - 1;
while (start <= end){
int mid = (start + end) / 2;
if(num == arr[mid]){
return mid;
}else if(num > arr[mid]){
start += 1;
}else {
end -= 1;
}
}
return -1;
}
/**
* 递归
* @param arr 已经升序好的int[]
* @param num 需要查找的数字
* @param start 区间开始下标
* @param end 区间结束下标
* @return 找到则返回下标,没找到则返回-1
*/
private static int binarySearchByRecursion(int[] arr,int num,int start,int end) {
int mid = (start + end) / 2;
if(num == arr[mid]){
return mid;
}else if(num > arr[mid]){
start += 1;
}else {
end -= 1;
}
if(start <= end && num != arr[mid]){
mid = binarySearchByRecursion(arr,num,start,end); //递归继续寻找
}else {
mid = -1;
}
return mid;
}
}
本文地址:https://blog.csdn.net/qq_44089205/article/details/110825668