Lets say I've got an ordered NSArray
of NSNumbers
:
假设我有一个有序的nsnumber NSArray
2, 4, 8, 15, 16, 20 // for simplicity let's treat it as array of int's instead of NSNumbers
Now I need to find closest index to let's say value == 19
.
现在我需要找到最接近的索引比如value = 19。
searchValue = 19;
minIndex = 0;
maxIndex = array.count - 1;
currentIndex = (int)floorf(maxIndex / 2.f);
while (maxIndex - minIndex == 1) {
if (array[currentIndex] < searchValue) { // go right
minIndex = currentIndex;
} else if (array[currentIndex] > searchValue) { // go left
maxIndex = currentIndex;
} else { // exact value, rather low probability of happening
return currentIndex;
}
currentIndex = (int)floorf((maxIndex - minIndex) / 2.f);
}
// let's check values around, who has smaller difference
int leftDifference = (currentIndex - 1 >= 0) ? abs(array[currentIndex - 1] - searchValue) : INT_MAX;
int rightDifference = (currentIndex + 1 < array.count) ? abs(array[currentIndex + 1] - searchValue) : INT_MAX;
int centralDifference = abs(array[currentIndex] - searchValue);
if (leftDifference < rightDifference && leftDifference < centralDifference) {
return currentIndex - 1;
} else if () {
return currentIndex + 1;
} else {
return currentIndex;
}
This is the fastest way I can imagine, maybe someone has different idea? How can I improve the algorithm?
这是我能想到的最快的方法,也许有人有不同的想法?如何改进算法?
I've took a look into egSOF question, but it search for value not index and does it by browsing all values. In case of index, we don't have to browse full array.
我研究过egSOF问题,但它搜索值而不是索引,并通过浏览所有值来实现。对于索引,我们不需要浏览整个数组。
1 个解决方案
#1
9
Lets assume you have an array of NSNumbers:
假设您有一个nsnumber数组:
NSArray *array = @[@(2), @(4), @(8), @(15), @(16), @(20)];
And you are looking for myValue
as below:
你在寻找我的价值如下:
NSNumber *myValue = @(17);
Use indexOfObject:inSortedRange:options:usingComparator
method to find the nearest index of array to you value. Binary search has O(log n) performance so is pretty fast.
使用indexOfObject:inSortedRange:options:使用比较器方法查找数组的最近索引。二进制搜索有O(log n)的性能,所以速度很快。
NSInteger searchIndex = MIN([array indexOfObject: myValue inSortedRange:NSMakeRange(0, array.count)
options:NSBinarySearchingFirstEqual | NSBinarySearchingInsertionIndex
usingComparator:^NSComparisonResult(NSNumber *obj1, NSNumber *obj2) {
return [obj1 compare:obj2];
}], [array count] - 1);
Then check if exists a number closest to yours myValue
on the searchIndex - 1
index:
然后在searchIndex - 1索引上检查是否存在一个与myValue最接近的数字:
if (searchIndex > 0) {
CGFloat leftHandDiff = ABS(((NSNumber *)array[searchIndex - 1]).floatValue - myValue.floatValue);
CGFloat rightHandDiff = ABS(((NSNumber *)array[searchIndex]).floatValue - myValue.floatValue);
if (leftHandDiff == rightHandDiff) {
//here you can add behaviour when your value is in the middle of range
NSLog(@"given value is in the middle");
} else if (leftHandDiff < rightHandDiff) {
searchIndex--;
}
}
NSLog(@"The nearest value to %f is %d in array at index %d", myValue.floatValue, array[searchIndex], searchIndex);
and voila! Now you now the closest value to myValue
.
瞧!现在你得到了最接近myValue的值。
Remember that your array
has to be sorted ascending to make this trick.
记住,数组必须按升序排序才能达到这个目的。
#1
9
Lets assume you have an array of NSNumbers:
假设您有一个nsnumber数组:
NSArray *array = @[@(2), @(4), @(8), @(15), @(16), @(20)];
And you are looking for myValue
as below:
你在寻找我的价值如下:
NSNumber *myValue = @(17);
Use indexOfObject:inSortedRange:options:usingComparator
method to find the nearest index of array to you value. Binary search has O(log n) performance so is pretty fast.
使用indexOfObject:inSortedRange:options:使用比较器方法查找数组的最近索引。二进制搜索有O(log n)的性能,所以速度很快。
NSInteger searchIndex = MIN([array indexOfObject: myValue inSortedRange:NSMakeRange(0, array.count)
options:NSBinarySearchingFirstEqual | NSBinarySearchingInsertionIndex
usingComparator:^NSComparisonResult(NSNumber *obj1, NSNumber *obj2) {
return [obj1 compare:obj2];
}], [array count] - 1);
Then check if exists a number closest to yours myValue
on the searchIndex - 1
index:
然后在searchIndex - 1索引上检查是否存在一个与myValue最接近的数字:
if (searchIndex > 0) {
CGFloat leftHandDiff = ABS(((NSNumber *)array[searchIndex - 1]).floatValue - myValue.floatValue);
CGFloat rightHandDiff = ABS(((NSNumber *)array[searchIndex]).floatValue - myValue.floatValue);
if (leftHandDiff == rightHandDiff) {
//here you can add behaviour when your value is in the middle of range
NSLog(@"given value is in the middle");
} else if (leftHandDiff < rightHandDiff) {
searchIndex--;
}
}
NSLog(@"The nearest value to %f is %d in array at index %d", myValue.floatValue, array[searchIndex], searchIndex);
and voila! Now you now the closest value to myValue
.
瞧!现在你得到了最接近myValue的值。
Remember that your array
has to be sorted ascending to make this trick.
记住,数组必须按升序排序才能达到这个目的。