二分查找算法

      今天在公司闲着蛋疼，网上瞎逛，偶然在InfoQ网站上看到一篇文章《计算机科学中最重要的32个算法》，原文地址：http://www.infoq.com/cn/news/2012/08/32-most-important-algorithms?utm_source=infoq&utm_medium=popular_links_homepage，里面就有二分查找算法，于是乎动手实现此算法，看自己是否掌握了，倒腾半天才写出来，汗颜哪。写下此文，一来回顾一下二分查找算法，而来警醒自己。

     一、概念

     二分查找算法也称折半查找，是一种在有序数组中查找某一特定元素的搜索算法。

      二、算法思想

      搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

      三、优缺点

      二分查找算法的优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。因此，二分查找算法适用于不经常变动而查找频繁的有序列表。

      四、复杂度分析

      (1) 时间复杂度

       二分查找每次把搜索区域减少一半，时间复杂度为。（n代表集合中元素的个数）

       (2) 空间复杂度

       。

       五、代码实现

       (1) 迭代实现

public static int binarySearch(int[] source, int target) {
  int bot = 1;
  int top = source.length - 1;
  while (bot <= top) {
    // 防止溢出
    int mid = (bot + top) >>> 1;
    if (target > source[mid]) {
        bot = mid + 1;
    } else if (target < source[mid]) {
        top = mid - 1;
    } else {
        return mid;
    }
  }
  return -(bot + 1);
}

        (2)递归实现 

/**
     * 二分查找递归实现
     *
     * @param source    源数组
     * @param target    目标值
     * @param lowIndex  低位索引
     * @param highIndex 高位索引
     * @return
     */
    private static int binarySearch(int[] source, int target, int lowIndex, int highIndex) {
        int mid = (lowIndex + highIndex) >>> 1;
        if (source[mid] == target) {
            return mid;
        } else if (lowIndex > highIndex) {
            return -(lowIndex + 1);
        } else {
            if (source[mid] > target) {
                return binarySearch(source, target, lowIndex, mid - 1);
            } else {
                return binarySearch(source, target, mid + 1, highIndex);
            }
        }
    }

     总结：1、最开始在写代码的时候，没有考虑到溢出。

             2、没想到用递归实现。