算法学习之二分法查找

以前在读书的时候没好好学习算法，出来工作后又都忘得差不多了，惭愧惭愧… 重新开始学习一些简单的算法，先从二分法开始吧！

二分法是当数据量很大时适宜采用，但是采用二分法的前提是，数据是有序不重复的。二分法又称折半查找，故名思意就是就是从中间开始比较查找，其基本思路是：假设数据是按升序排序的，对于给定值 x，从序列的中间位置开始比较，如果当前位置值等于 x，则查找成功；若 x 小于当前位置值，则在数列的前半段中查找；若 x 大于当前位置值则在数列的后半段中继续查找，直到找到为止。所以二分法查找的速度比较快,次数比较少,性能比较好；因此相对来说其删除和插入操作就不是那么灵活了。

下面就已一个小例子来看看：

/**
 * 二分法demo
 * @author Richard
 */
public class Demo1 {

public static void main(String[] args) {
new Thread(new Runnable() {

@Override
public void run() {
int[] array = new int[10000000];
for (int i = 0; i < array.length; i++) {
                    array[i] = i;
                }
long time = System.currentTimeMillis();
                System.out.println(searchNumber(array, 1576111));
                System.out.println(searchNumber(array, 157611));
                System.out.println("计算时间毫秒: " + (System.currentTimeMillis() - time));

                time = System.currentTimeMillis();
                System.out.println(searchRecursion(array, 0, array.length - 1, 1576111));
                System.out.println(searchRecursion(array, 0, array.length - 1, 157611));
                System.out.println("递归二分法计算时间毫秒: " + (System.currentTimeMillis() - time));
            }
        }).start();
    }

/**
 * 二分法查询该值在数组中的位置
 * 
 * @param array
 * 要查询的数组
 * @param searchValue
 * 要查询的值
 * @return -1表示没有查询到
 */
private static int searchNumber(int[] array, int searchValue) {
if (array == null)
return -1;

int start = 0;
int end = array.length - 1;
int mid = 0;
while (start <= end) {
// 每次取中间位置进行查找
            mid = (start + end) / 2;
if (searchValue < array[mid]) {
                end = mid - 1;
            } else if (searchValue > array[mid]) {
                start = mid + 1;
            } else {
return mid;
            }
        }
return -1;
    }

/**
 * 二分法递归查询
 * 
 * @param array
 * 要查询的数组
 * @param start
 * 起始位置
 * @param end
 * 结束位置
 * @param searchValue
 * 要查询的值
 * @return -1表示没有查询到
 */
private static int searchRecursion(int[] array, int start, int end, int searchValue) {
if (array == null)
return -1;

if (start <= end) {
// 每次取中间位置进行查找
int mid = (start + end) / 2;
if (searchValue < array[mid]) {
return searchRecursion(array, start, mid - 1, searchValue);
            } else if (searchValue > array[mid]) {
return searchRecursion(array, mid + 1, end, searchValue);
            } else {
return mid;
            }
        }
return -1;
    }
}

我想上面的代码分别介绍了两种二分法的实现方式，看起来应该通俗易懂吧！但是其实上面的代码还可以提高查找效率，比如取中间值时可以用位运算，如下：

private static int searchNumberV(int[] array, int searchValue) {
if (array == null)
        return -1;

int start = 0;
int end = array.length - 1;
int mid = 0;
while (start <= end) {
mid = (start + end) >>> 1;
if (searchValue < array[mid]) {
end = mid - 1;
        } else if (searchValue > array[mid]) {
            start = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

有兴趣的可以研究下这个，https://github.com/cheyiliu/All-in-One/wiki/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE
二分法的实现。