[java] 二分法查找

2019-11-06 07:45:43

字体：大中小

来源：转载

供稿：网友

首先上二分法java实现的代码

import java.util.Arrays;public class BinarySearch { public static int rank(int key, int[] a) { //数组必须是有序的 int lo = 0; int hi = a.length - 1; while(lo <= hi) { //被查找的键要么不存在，要么必然存在于a[lo...hi]之中 int mid = lo + (hi - lo) / 2; if(key < a[mid]) { hi = mid - 1; }else if(key > a[mid]) { lo = mid + 1; }else { return mid; } } return -1; } public static void main(String[] args) { int[] arr = new int[] {1,2,7,5,9,10}; Arrays.sort(arr); System.out.PRintln(Arrays.toString(arr)); int index = BinarySearch.rank(7, arr); System.out.println(index); }}

要求：传入的数组必须是排好序的逻辑：先将数组分为中间，左边数组，右边数组。如果要查找的key正好是中间的则反回索引，如果key 大于 arr[mid],则在右面继续查找，反之在左面查找。当到达边界还没找到时，也就是lo==hi时，lo++ 会大于hi，或者 hi– 会小于lo。则循环终止，返回-1

我们先谈谈mid值的计算

//如果数组的长度为奇数数组正好被平均的分为左右两个要查找数组//如数组为 int[] arr = new int{1,2,3,4,5}//则数组的mid 为 (arr.length - 1) / 2 = 2//mid左边的数组为{1，2}，右面为 {4， 5}//如果数组的长度为偶数//如数组为 int[] arr = new int{1,2,3,4,5，6}//则数组的mid 为 (arr.length - 1) / 2 = 2//mid左边的数组为{1，2}，右面为 {4， 5， 6}

上一篇：java的BeanUtils.copyProperties会把为数据源对象中数字包装对象为null的值改成0赋值给操作对象的属性

下一篇：Java原子操作实现--锁与循环CAS