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的时候，系统是用的更为高效的位移运算，还是很有借鉴意义的。