算法学习————二分法

折半搜索,二分法

二分法又叫折半搜索，是比较简单和基础的算法。主要是将一个有序的数组不断划分为两部分，直到找到需要的值为止，是分治法的一种典型应用。
二分法比较简单但是在使用之前一定要对参数做判断，比如low与high的大小，mid的取值；二分法一般应用与有序数组中，通常不应用与链表中，由于链表查询速度慢，使用二分法查找效率更低。数组的二分法查找实现有两种方法一种使用递归，另外一种不使用递归。下面分别给出递归和非递归的实现：

递归实现
 /**
 * <p>二分算法的递归实现</p>
 * @param low 起始位置
 * @param high 结束位置
 * @param a 查询的数组
 * @param key 查询关键字
 * @return
 * int
 *
 */
public int binarySerach(int low,int high,int[] a ,int key){
   int mid;
   if(low>high){
       return -1;
   }
   if(low<0||high>a.length){
       return -1;

   }
   //mid=(high+low)/2; //当数据足够大时可能溢出
   mid=low+(high-low)/2;//保证计算出来的mid，一定大于low，小于high，不存在溢出的问题。
  if(low<high){
       if(a[mid]>key){
           return binarySerach(low, mid, a, key);
       }else if(a[mid]<key){
           return binarySerach(mid+1, high, a, key);
       }else if(a[mid]==key){
           return mid;
       }
  }else if(low==high){
       if(a[mid]==key){
           return mid;
       }else{
           return -1;
       }

  }else{
      return -1;
  }
return -1;

}

以上是二分算法的递归实现，在Java的Arrays类有二分的非递归实现这里直接贴代码：

  /**
     * <p>比较之前的数据校验</p>
     *
     * @param length 总长度
     * @param fromIndex 开始位置
     * @param toIndex 结束位置
     * void
     *
     */
    private static void rangeCheck(int length, int fromIndex, int toIndex) {
        if (fromIndex > toIndex) {
            throw new IllegalArgumentException(
                "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
        }
        if (fromIndex < 0) {
            throw new ArrayIndexOutOfBoundsException(fromIndex);
        }
        if (toIndex > length) {
            throw new ArrayIndexOutOfBoundsException(toIndex);
        }
    }

   private static int binarySearch0(long[] a, int fromIndex, int toIndex,
            long key) {
            int low = fromIndex;
            int high = toIndex - 1;
            while (low <= high) {
            int mid = (low + high) >>> 1;
        long 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.}
---

额外拓展

二分法主要应用与查找递增或递减序列，但是当序列并非严格单调性的时候就需要使用三分法。三分法主要应用求极值。设置中点
mid=(l+r)/2
mid2=(mid+r)/2
根据中点的值大小继续缩小范围

public int  serach(int left,int right){
   int mid=(left+right)/2;
   int mid2=(mid+right)/2;
  while(high>=low){
   if(f(mid)>f(mid2)){
       right=mid;
   }else{
       left=mid2;
   }
   }
  }