本文中使用的配圖以及一些案例來源于圖解算法一書威始，借助書中的案例，我使用OC語法實現(xiàn)其中的案例，這樣有助于學(xué)習(xí)OC的小伙伴更好的理解其中的實現(xiàn)過程剩燥，如果本文對你起到了一定的作用，那么請給一顆小星星哦 ??????。
二分查找是一種算法灭红，其輸入一個有序的元素列表侣滩，如果要查找的元素包含在列表中，二分查找返回其位置变擒，否在返回NULL.
舉個栗子
小明和小芳玩猜謎游戲君珠。小芳在紙上寫下一個1-100以內(nèi)的一個數(shù)字，讓小明去猜數(shù)字是多少娇斑。如果小明從1開始遞增猜測 假如小芳寫的數(shù)字是99 那么小明需要猜測99次策添。
屏幕快照.png
這是簡單查找，更準(zhǔn)確說是傻找毫缆。
使用二分法查找是一種更佳的方式
下面是一種更佳的猜法唯竹。
屏幕快照.png
小了但是排除了一半的數(shù)字，至此小明知道了1～50都小了接下來小明猜測75苦丁，大了那么余下的數(shù)字排除一半浸颓，接下來，你猜測63（50和75中間的數(shù)字）旺拉，這就是二分法查找产上。
屏幕快照.png
一般而言對于包含N個元素的列表，用二分法查找最多需要log2n步账阻，而簡單查找最多需要n步蒂秘。
OC實現(xiàn)案例。
首先淘太，定義個遞增有序的數(shù)組（數(shù)組范圍1-100）姻僧，如果我想找到數(shù)字75（元素）在數(shù)組中的位置
屏幕快照.png
每次都檢查中間的元素
NSArray *numberArray = @[@1, @3, @27, @36, @42, @70, @82];
NSInteger searchNum = 70;//需要查找的元素
NSInteger mid;//中間元素的位置
NSInteger low = 0;
NSInteger high = [numberArray count] - 1;
//low. 和high用于跟蹤要在其中查找的列表部分
BOOL found = NO;//定義一個bool值用來記錄是否查找到需要查找的元素
while (low <= high) {//只要范圍沒有縮小到只包含一個元素
mid = (low + high)/2;//中間位置
if (searchNum == [numberArray[mid] intValue]) {
NSLog(@"我們發(fā)現(xiàn)數(shù)量!它是===> %@", numberArray[mid]);
found = YES;
break;
} else if (searchNum < [numberArray[mid] integerValue]) {
high = mid - 1;//猜測的數(shù)字大了的話，那么就修改high的值
} else if (searchNum > [numberArray[mid] integerValue]) {
low = mid + 1;//如果猜測的數(shù)字小了 那么就增加low的值
}
}
if (!found) {
NSLog(@"這個數(shù)字沒有找到.");//沒有指定的元素
}
