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);