OC实现二分法查找

本文中使用的配图以及一些案例来源于图解算法一书，借助书中的案例，我使用OC语法实现其中的案例，这样有助于学习OC的小伙伴更好的理解其中的实现过程，如果本文对你起到了一定的作用，那么请给一颗小星星哦 😊😊😊。

二分查找是一种算法，其输入一个有序的元素列表，如果要查找的元素包含在列表中，二分查找返回其位置，否在返回NULL.

举个栗子
小明和小芳玩猜谜游戏。小芳在纸上写下一个1-100以内的一个数字，让小明去猜数字是多少。如果小明从1开始递增猜测 假如小芳写的数字是99 那么小明需要猜测99次。

屏幕快照.png

这是简单查找，更准确说是傻找。

使用二分法查找是一种更佳的方式

下面是一种更佳的猜法。

屏幕快照.png

小了但是排除了一半的数字，至此小明知道了1～50都小了接下来小明猜测75，大了那么余下的数字排除一半，接下来，你猜测63（50和75中间的数字），这就是二分法查找。

屏幕快照.png

一般而言对于包含N个元素的列表，用二分法查找最多需要log2n步，而简单查找最多需要n步。

OC实现案例。
首先，定义个递增有序的数组（数组范围1-100），如果我想找到数字75（元素）在数组中的位置

屏幕快照.png

 每次都检查中间的元素
 NSArray *numberArray = @[@1, @3, @27, @36, @42, @70, @82];
    NSInteger searchNum = 70;//需要查找的元素
    NSInteger mid;//中间元素的位置
    NSInteger low = 0;
    NSInteger high = [numberArray count] - 1;
//low. 和high用于跟踪要在其中查找的列表部分
    BOOL found = NO;//定义一个bool值用来记录是否查找到需要查找的元素

    while (low <= high) {//只要范围没有缩小到只包含一个元素

        mid = (low + high)/2;//中间位置

    if (searchNum == [numberArray[mid] intValue]) {

        NSLog(@"我们发现数量!它是===> %@", numberArray[mid]);

        found = YES;

        break;

    } else if (searchNum < [numberArray[mid] integerValue]) {
  
        high = mid - 1;//猜测的数字大了的话，那么就修改high的值

    } else if (searchNum > [numberArray[mid] integerValue]) {

        low = mid + 1;//如果猜测的数字小了 那么就增加low的值

    }

        }

        if (!found) {
            NSLog(@"这个数字没有找到.");//没有指定的元素
        }