前言
从前端转型搞iOS近三年了，最近技术进阶很艰难，反思和整理之后，觉得是『内功』修炼不够，所以现在的我要忘掉所有招式，回归基本功的修炼，希望有缘看到本篇文章的大神，可以不吝指导，谢谢。
都说天下武功出少林，同样，所有的编程开发语言中万变不离其宗的应该就是算法和理论了，算法可算是程序的灵魂。
要想有个强大的灵魂，我打算重新修炼基本功——算法。
先从『二分法』开始：
算法原理
假设需要查找的值为x，检索的数组为array。
- 确定查找范围 from = 0，end = array.count - 1，计算中项 middle= (from + end) / 2。
- 若 array[middle] = x 或 from >= end, 则结束查找；否则，向下继续。
- 若 array[middle] < x, 说明待查找的元素值只可能在比中项元素大的范围内，则把 middle + 1 的值赋给from，并重新计算middle，转去执行步骤2；
- 若 array[middle] > x，说明待查找的元素值只可能在比中项元素小的范围内，则把 middle - 1 的值赋给end，并重新计算middle，转去执行步骤2。
适用范围
二分法是一种非常高效的数据查找算法，通常适用二分法的都有以下特征：
- 数据量大；
- 数据为有序的；
- 需要在大量数据中定位某个值或找出某个值的索引值；
运用
场景：在一个升序的数组 [21, 23, 25, 27, ... , 53 ]中获取 31 的索引值，如31不在数组中，则返回-1；
- (void)viewDidLoad {
[super viewDidLoad];
NSArray *array = @[@11, @23, @29, @31, @33, @35, @37, @47, @71, @99];
NSInteger key = 23;
NSLog(@"key 在数组 array 中的索引是：%ld", [self getIndexOfKey:key atArray:array]);
}
- (NSInteger)getIndexOfKey: (NSInteger)key atArray: (NSArray *)array {
NSInteger min = 0, mid = 0, max = array.count-1;
while (min <= max) {
mid = (min + max) / 2;
if (key == [array[mid] integerValue]) {
return mid;
}
else if (key > [array[mid] integerValue]) {
min = mid + 1;
}
else if (key < [array[mid] integerValue]) {
max = mid - 1;
}
}
return -1;
}
https://baike.baidu.com/item/二分法查找/9751511?fr=aladdin
http://www.baike.com/wiki/二分法
