27
2017
09

数据结构与算法,二分查找

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 就可以了

退出循环后,判断 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) { // 相邻就退出
            start = mid;
        } else if ([source[mid] integerValue] > target) {
            end = mid;
        } else {
            end = mid;
        }
    }
    if ([source[start] integerValue] == target) {
        return start;
    }
    if ([source[end] integerValue] == target) {
        return end;
    }

    return -1;
}
上一篇:Xlistview 应用 下一篇:Swift Label计算高度