美文网首页
IOS 二分法查找目标值所在索引

IOS 二分法查找目标值所在索引

作者: 六两 | 来源:发表于2022-04-01 19:07 被阅读0次

    以下为顺序数组筛查,请自行排序

    如题,直接开始

        int searchNum = 47;
        NSArray *numberArray = @[@(11),@(15),@(22),@(26),@(33),@(37),@(44),@(47),@(77),@(87)];
        int middle = 0;//中位值索引
        int low = 0;//低位值索引
        long int high = [numberArray count] - 1;//高位索引
        //1.在🌟升序数组🌟中找到目标值的坐标
        BOOL found = NO;//定义一个bool值用来记录是否查找到需要查找的元素
        while (low <= high) {//只要范围没有缩小到只包含一个元素
            middle = (low + high) * 0.5;//中间位置 乘法比除法快
            if (searchNum == [numberArray[middle] intValue]) {
                NSLog(@"目标值已找到===>在第%d位", middle);
                found = YES;
                break;
            } else if (searchNum < [numberArray[middle] integerValue]) {
                high = middle - 1;//猜测的数字大了的话,那么就high - 1
            } else if (searchNum > [numberArray[middle] integerValue]) {
                low = middle + 1;//如果猜测的数字小了 那么就增加low + 1
            }
        }
        if (!found) {
                    
            NSLog(@"这个数字没有找到.");
               
        }
        low = 0;
        high = [numberArray count] - 1;;
        middle = 0;
        
        //2.在🌟升序数组🌟中找到与目标值相差最小的值的坐标
        while (low<= high) {
            middle = (low +high) *0.5;
            
            if (labs([numberArray[middle + 1] integerValue] - searchNum) > labs([numberArray[middle] integerValue] - searchNum)) {
                //计算两个中位索引的差值,如果大于就让high-1,持续下去就会与low相等
                high = middle - 1;
            }else{
                low = middle + 1;
            }
            
            
        }
        //循环判断结束,middle和middle+1 是最接近目标值的两个索引,做最后的一次比较即可
        NSInteger index = (labs([numberArray[middle + 1] integerValue] - searchNum) > labs([numberArray[middle] integerValue] - searchNum)) ? middle :(middle + 1);
        NSLog(@"目标值%d,与第%ld位的值最接近",searchNum,index);
    

    相关文章

      网友评论

          本文标题:IOS 二分法查找目标值所在索引

          本文链接:https://www.haomeiwen.com/subject/uyiajrtx.html