Java实现二分查找法

浏览数：18 / 时间：2015年06月08日

1. 二分查找优缺点

说明：二分查找法又成为折半查找法

优点：比较次数比较少，查找速度比较快，平均性能好

缺点：要求待查表为有序的，插入数据比较困难

适应场合：用于不经常变动且查找频繁的有序列表

2. 二分查找原理

如果有这些有序数据： 1, 2, 3, 4, 5

我们需要查找到：2

第一步：(0+4)/2=2 （其中0，4是最小和最大元素的数组下标）

第二步：比较2和第一步取到的下标为2的数值，结果2比3小，所以要查的数肯定在左侧

以此寻找下去就可以找到自己想要找到的那一个值

3. 二分查找法的实现



/**
 * FileName:    BinarySearchDemo.java
 * Date:        2014年4月6日
 * Autoher:     [email protected]
 * CopyWrite:   searchpcc@2014
 * site:        http://searchpcc.cnblogs.com
 */
package com.searchpcc.binarysearch;
import java.util.Arrays;
/**
 * 
 * className: BinarySearchDemo
 * desc:         二分查找法实现      
 * author:    searchpcc
 * date:      2014年4月6日
 *
 */
public class BinarySearchDemo {
    public static int binarysearch(int[] number, int n) {
        int start = 0; // 开始位置
        int end = number.length-1; // 结束位置
        int middle; 
        while (start <= end) {
            middle = (start+end)/2; // 求中间位置
            // 要找的值已经找到
            if (number[middle] == n) {
                return middle;
            } else if (number[middle] < n) {
                start = middle+1;
            } else if(number[middle] > n){
                end = middle-1;
            } 
        }
        return -1; // 没有就找不到
    }
    public static void main(String[] args) {
        int[] number = {1,3,2,4,5,7,6,8};
        // 第一步：排序
        Arrays.sort(number);
        int index = binarysearch(number, 6);
        System.out.println(index);
    }
}