泉州网站制作网页,尉氏做网站,博星卓越电子商务网站建设实训平台,观影楼网站文章目录 Java实现二分法的案例#xff0c;什么是二分法二分法实现 Java实现二分法的案例#xff0c;什么是二分法
二分法
概念#xff1a;
二分法#xff08;Bisection method#xff09; 即一分为二的方法#xff0c;又叫折半查找方法。把一组有序数列分为左右两部分… 文章目录 Java实现二分法的案例什么是二分法二分法实现 Java实现二分法的案例什么是二分法
二分法
概念
二分法Bisection method 即一分为二的方法又叫折半查找方法。把一组有序数列分为左右两部分从这组数字的中间位置开始找如果中间位置的数等于目标数则直接返回如果中间位置的数大于目标数则从左边部分查找如果小于目标数则从右边部分查找重复以上过程直到找到满足条件的记录使查找成功。
时间复杂度 都是 O(log2 N)
空间复杂度 非递归方式 空间复杂度是O(1); 递归方式 空间复杂度O(log2N )
实现
1. 递归方式 public static int binarySearchRecursive(int[] arr, int low, int high, int key) {//边界条件如果目标数没有在数组范围内即比最左边的数小比最右边的数大if (arr null || arr.length 0 || arr[low] key || arr[high] key || low high) {return -1;}// 获取中间位置下标int mid (low high) / 2;// 将中间位置的数和目标数作比较如果中间位置的数等于目标数则直接返回下标// 如果中间位置的数大于目标数则将左边部分用递归方法继续查找如果小于目标数则从右边部分用递归方法继续查找if (arr[mid] key) {return mid;} else if (arr[mid] key) {return binarySearch(arr, low, mid - 1, key);} else {return binarySearch(arr, mid 1, high, key);}}// 测试下从一组数中找3输出数组下标public static void main(String[] args) {int[] arr {2, 3, 5, 7, 9, 78, 90, 167};System.out.println(binarySearchRecursive(arr, 0, (arr.length) - 1, 3));}
2. 非递归方式 public static int binarySearch(int[] arr, int key) {int low 0;int high arr.length - 1;while (low high) {int middle (low high) / 2;if (key arr[middle]) {high middle - 1;} else if (key arr[middle]) {low middle 1;} else {return middle;}}return -1;}// 测试下从一组数中找3输出数组下标public static void main(String[] args) {int[] arr {2, 3, 5, 7, 9, 78, 90, 167};System.out.println(数组下标binarySearch(arr, 3));}
3.非递归
/*** 二分查找* param srcArray 源数组* param des 目标元素* return 如果找到则返回索引位置找不到则返回-1*/
public static int binarySearch(int[] srcArray, int des) {//定义初始最小、最大索引int start 0;int end srcArray.length - 1;//确保不会出现重复查找越界while (start end) {//计算出中间索引值 逻辑右移 也就是 int middle (end start)/2int middle (end start)1 ;//防止溢出if (des srcArray[middle]) {return middle;//判断下限} else if (des srcArray[middle]) {end middle - 1;//判断上限} else {start middle 1;}}//若没有则返回-1return -1;
}
