java算法（二）折半查找

1.引言

折半查找算法，算是这本书中最简单的算法，以前在大学学的时候用的c语言编写的算法。换成用java来写，发现代码量不是一般的少。

2.正题

折半算法的核心思想：首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将序列分成前、后两个序列，如果中间位置记 录的关键字大于查找关键字，则进一步查找前一序列，否则进一步查找后一序列。重复以上过程，直到找到满足条件的记录，使查找成功，或直到序列不存在为止，此时查找不成功。

要求：待查找的序列是：一个顺序序列。

代码如下：

/**
 * Created by wxy on 2017/5/14.
 * 折半查找
 */
public class BinarySerach {

    public static void main(String args[]){
        int math=56;
        List<Integer>mlist=new ArrayList<>();
        for (int i=0;i<100;i++){
            mlist.add(i);
        }
        int low=0;
        int hight=mlist.size()-1;
        int half = -1;
        while (low<=hight){
            half=(low+hight)/2;
            if (mlist.get(half)>math){
                hight=half;
            }else if (mlist.get(half)<math){
                low=half;
            }else {
                break;
            }
        }
        System.out.println(half);
    }
}

时间复杂度O()=O(logn)