写二分的时候最纠结的就是循环条件，而且特别容易出现死循环。
来看一个最经典的二分：给你一个数组，再给你个 target，找到 target 在数组中的位置，找不到就返回 - 1。有些题目是让你找第一个出现的位置，也有让你找到最后出现的位置。
1.时间复杂度：
每次能去掉一半即 logn
2.实现方式：
while循环 与 递归
我更推荐 while 循环，因为递归有个潜在的问题就是 stack over flow(堆栈溢出)，而且在实际工程中是尽量避免递归的。虽然递归写起来方便，也不容易出错。
3.实现关键点
我总结了下，一共有以下四点
start + 1 < end
这个是 while 循环条件，即退出循环的条件是 start +1 >= end,首先来看 start + 1 == end 这个时候，start 和 end 是相邻的关系。start > end 两者相交了。而且这样的写法不可能出现死循环，比如下面这种写法很容易就出现了死循环。
while (start < end) {// 1,2
mid = ...; //1
if (...) {
start = mid;
} else {
end = mid;
}
}
- ** mid = start + (end - start)/2**
这个写法看起来很妖艳儿，有点装逼，实际上能还是很有用的。因为传统的写法 (start + end) / 2 ，这样有个潜在的问题，就是如果 start ，end 足够大的话就会出现溢出的问题。这个点可以看出工程师还是很细心的。
- ** source[mid] ==, <, > **
循环开始，根据mid和target的关系，看看怎么移动 end、start 指针，根据具体题目移动。一般来说等于 mid 就可以了
- ** source[start] source[end] ? target**
退出循环后，判断 start 、 end 和 target 的关系。
下面直接上代码了，这样写的好处是只用处理最后两个数的逻辑，很容易扩展。类似于递归到最底层只处理1个或者的关系。
+ (NSInteger)binarySearch:(NSArray *)source target:(NSInteger)target {
if (source.count == 0) {
return -1;
}
NSInteger start = 0;
NSInteger end = source.count - 1;
NSInteger mid = 0;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if ([source[mid] integerValue] == target) { // 相邻就退出
return mid;
} else if ([source[mid] integerValue] < target) {
start = mid;
} else {
end = mid;
}
}
if ([source[start] integerValue] == target) {
return start;
}
if ([source[end] integerValue] == target) {
return end;
}
return -1;
}
