Java基础复习 查找算法之二分法

package com.arjun; /** * Created by Arjun on 16/9/26. * 查找算法之二分法： * 假如有一个升序排列，那么查找的时候，会从数组的中间位置开始，与中间位置值相比较，如果要查找的值大于中间位置元素，那么继续在数组的后面继续一半查找；如果相等，则返回 ； 如果小于则在前面进行一半查找，直到无法二分数组结束； */ public class BinarySearch { public static void main(String[] args) { //定义一个测试升序数组 int asc[] = {1, 3, 56, 334, 343, 532, 734, 883, 983, 993, 999, 2343};//999 //定义一个降序数组 int desc[] = {1000, 999, 123, 22, 11, 2, 1, 0, -21, -1212}; //要查找的元素 int fn = 3; BinarySearch bs = new BinarySearch(); boolean findAsc = bs.binarySearch(fn, asc); boolean findDesc = bs.binarySearch(fn, desc); System.out.print(findAsc + "," + findDesc); } /** * @param fn 查找值 * @param arr 有序数组 * @return true为存在 */ private boolean binarySearch(int fn, int arr[]) { int front = 0; int tail = arr.length - 1; boolean isasc = arr[0] < arr[1];//这里暂时没有考虑有相等元素的情况 while (front <= tail) { int middle = (front + tail) / 2; if (arr[middle] == fn) { return true; } else if (arr[middle] < fn) { if (isasc) { front = middle + 1; } else tail = middle - 1; } else { if (!isasc) { front = middle + 1; } else tail = middle - 1; } } return false; } }

二分法的使用场景，只针对有序排列的各种数组或集合。

另外，在查看Arrays类的时候，发先系统其实也提供了二分搜索算法的实现， 就是static int binarySearch方法

public static int binarySearch(int[] a, int key)... public static int binarySearch(int[] a, int fromIndex, int toIndex,int key)...

来看下这个参数多的方法

public static int binarySearch(int[] a, int fromIndex, int toIndex, int key) { rangeCheck(a.length, fromIndex, toIndex); return binarySearch0(a, fromIndex, toIndex, key); }

在进行binarySearch之前进行了，rangeCheck是什么鬼，来看一下是代码是怎么写。

/** * Checks that {@code fromIndex} and {@code toIndex} are in * the range and throws an exception if they aren't. */ private static void rangeCheck(int arrayLength, int fromIndex, int toIndex) { if (fromIndex > toIndex) { throw new IllegalArgumentException( "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")"); } if (fromIndex < 0) { throw new ArrayIndexOutOfBoundsException(fromIndex); } if (toIndex > arrayLength) { throw new ArrayIndexOutOfBoundsException(toIndex); } }

rangeCheck原来就是对输入下标的一个检查，binarySearch0才是实现的重点。

// Like public version, but without range checks. private static int binarySearch0(int[] a, int fromIndex, int toIndex, int key) { int low = fromIndex; int high = toIndex - 1; while (low <= high) { int mid = (low + high) >>> 1; int midVal = a[mid]; if (midVal < key) low = mid + 1; else if (midVal > key) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found. }

简单说一下，查到，则返回相应的下标，否则返回一个负数； … 跟上边自己的其实是一样的， 不过系统的写法更高大上， 除2的时候，系统是用的更为高效的位移运算，还是很有借鉴意义的。

aikongmeng 认证博客专家 RxJava 性能优化 Android Jetpack _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ ( T | o ) ( Y | o | u | t | h | , | T | o ) ( S | i | m | p | l | e | ! ) \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/