二分查找又稱折半查找夕凝，優(yōu)點是比較次數(shù)少宝穗，查找速度快，平均性能好码秉，占用系統(tǒng)內(nèi)存較少讽营；其缺點是要求待查表為有序表，且插入刪除困難泡徙。因此橱鹏，折半查找方法適用于不經(jīng)常變動而查找頻繁的有序列表。首先堪藐，假設表中元素是按升序排列莉兰，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等礁竞，則查找成功糖荒；否則利用中間位置記錄將表分成前、后兩個子表模捂，如果中間位置記錄的關鍵字大于查找關鍵字捶朵，則進一步查找前一子表，否則進一步查找后一子表狂男。重復以上過程综看，直到找到滿足條件的記錄，使查找成功岖食，或直到子表不存在為止红碑，此時查找不成功。
要求
- 必須采用順序存儲結構。
- 必須按關鍵字大小有序排列析珊。
時間復雜度可以表示O(h)=O(log2n)
- (int)p_BinSearch:(NSMutableArray *)arrSort key:(int)key{
int mid;
int start = 0;
int end = (int)arrSort.count - 1;
while (start <= end) {
mid = (end - start) / 2 + start;
if (key < mid) {
end = mid - 1;
}
else if (key > mid) {
start = mid + 1;
}
else {
return mid;
}
}
return -1;
}
