（3）iOS程序猿算法学习——二分查找「Binary Searc

写二分的时候最纠结的就是循环条件，而且特别容易出现死循环。
来看一个最经典的二分：给你一个数组，再给你个 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;
}