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

2022-04-01  本文已影响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);
上一篇下一篇

猜你喜欢

热点阅读