Objective-C实现二分查找和插值查找

```/**
* 二分查找循环实现
*/
- (NSUInteger)binarySearch:(NSArray<NSNumber *> *)srcArray number:(NSNumber *)des {
NSUInteger low = 0;
NSUInteger high = srcArray.count - 1;
NSInteger middle = 0;
while (low <= high && low <= srcArray.count - 1 && high <= srcArray.count - 1) {
middle = (low + high) >> 1;
// 或者
// middle = ((high - low) >> 1) + low;
if ([des integerValue] == [srcArray[middle] integerValue]) {
return middle;
} else if ([des integerValue] < [srcArray[middle] integerValue]) {
high = middle - 1;
} else {
low = middle + 1;
}
}
return -1;
}

/**
* 二分查找递归实现
*/

- (NSUInteger)binarySearch:(NSArray<NSNumber *> *)srcArray key:(NSNumber *)key low:(NSUInteger)low high:(NSUInteger)high {
// 防止low和high越界
if (low > high || low > srcArray.count - 1 || high > srcArray.count - 1) {
return -1;
}
NSUInteger middle = (low + high) >> 1;
if (srcArray[middle] == key) {
return middle;
} else if (srcArray[middle] > key) {
return [self binarySearch:srcArray key:key low:low high:middle - 1];
} else {
return [self binarySearch:srcArray key:key low:middle + 1 high:high];
}

return -1;
}

/**
* 插值查找循环实现
*/
- (NSUInteger)insertSearch:(NSArray<NSNumber *> *)srcArray number:(NSNumber *)des {
NSUInteger low = 0;
NSUInteger high = srcArray.count - 1;
NSInteger middle = 0;
while (low <= high && low <= srcArray.count - 1 && high <= srcArray.count - 1) {
middle = low + ([des integerValue] - [srcArray[low] integerValue])/([srcArray[high] integerValue] - [srcArray[low] integerValue]) * (high - low);
// 防止middle越界
if (middle > high || middle < low) {
return  -1;
}
if ([des integerValue] == [srcArray[middle] integerValue]) {
return middle;
} else if ([des integerValue] < [srcArray[middle] integerValue]) {
high = middle - 1;
} else {
low = middle + 1;
}
}
return -1;
}

/**
* 插值查找递归实现
*/

- (NSUInteger)insertSearch:(NSArray<NSNumber *> *)srcArray key:(NSNumber *)des low:(NSUInteger)low high:(NSUInteger)high {
// 防止low和high越界
if (low > high || low > srcArray.count - 1 || high > srcArray.count - 1) {
return -1;
}

NSUInteger middle = low + ([des integerValue] - [srcArray[low] integerValue])/([srcArray[high] integerValue] - [srcArray[low] integerValue]) * (high - low);
// 防止middle越界
if (middle > high || middle < low) {
return -1;
}
if ([srcArray[middle] integerValue]  == [des integerValue]) {
return middle;
} else if (srcArray[middle] > des) {
return [self insertSearch:srcArray key:des low:low high:middle - 1];
} else {
return [self insertSearch:srcArray key:des low:middle + 1 high:high];
}
return -1;
}```

0 条评论

相关文章

2017"百度之星"程序设计大赛 - 复赛1005&&HDU 6148 Valley Numer【数位dp】

Valley Numer Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768...

2864

Java语言中：float数据类型在内存中是怎么存储的？

============================================================================= ja...

1661

981

1772

4928

5206

2845