OC算法04：二分查找探索

二分查找

1. 简介

二分查找(也称折半查找)是很常见的一种在数组中查找数据的算法,作为一名程序员是应该必须会的。

2. 基本思想

获取数组的中间值，将数组分割成两份，利用查找的值跟中间值进行比较，如果查找的值大于中间值，就在数组的右边进行查找；如果查找的值小于中间值，就在数组的左边进行查找。如此循环的执行下去，最终找到符合的值。

3. 优缺点

1）优点：

• 速度快
• 比较次数少
• 性能好

2）缺点：

• 必须是一个有序的数组（升序或者降序）
• 适用范围：适用不经常变动的数组

4. 复杂度

时间复杂度就变成了O(logN)

5. 具体代码

- (void)viewDidLoad {
    [super viewDidLoad];
    NSArray * arr = @[@1,@3,@5,@6,@8,@15,@20];
    NSInteger result = [self binarySearchTarget:@1 inArray:arr];
    NSLog(@"%ld",(long)result);
}

// 在某个数组中搜索目标
- (NSInteger)binarySearchTarget:(NSNumber *)target inArray:(NSArray *)arr{
    //如果数组无元素，则返回
    if (arr.count < 1) {
        return -1;
    }
    
    //如果数组有元素
    //定义三个变量 第一个值下标、最后一个值下标、中间值下标
    NSInteger start = 0;
    NSInteger end = arr.count - 1;
    NSInteger mid = 0;
    //如果开始和结束中间还有元素，则循环
    while (start < end - 1) {
        //会有一些朋友看到有些人是( start + end ) / 2这样写的,但是这样写有一点不好,就是start+end会出现整数溢出的情况,如果存在溢出,你再除以2也是没有用的,所以不能这么写
        mid = start + (end - start) / 2;
        //如果中间值大于目标值
        if ([arr[mid] intValue] > [target intValue]) {
            //中间值做为最后一个值，在前半段再进行相同的搜索
            end = mid;
        }
        //如果中间值小于或等于目标值
        else {
            start = mid;
        }
    }
    
    //考虑到边界问题，所以下面这俩个必须写
    //如果第一个值和目标值相等则获取第一个值的下标
    if ([arr[start] intValue] == [target intValue]) {
        return start;
    }
    
    //如果最后一个值和目标值相等则获取最后一个值的下标
    if ([arr[end] intValue] == [target intValue]) {
        return end;
    }
    
    return -1;
}

查看打印结果

2020-08-26 18:06:44.754180+0800 iOS-OC之二分查找[49535:2738585] 0