1.引言
折半查找算法，算是這本書中最簡單的算法帝嗡，以前在大學學的時候用的c語言編寫的算法峡蟋。換成用java來寫坟桅，發(fā)現代碼量不是一般的少华望。
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)
