NSArray & # 8594; Finding the closest value is the fastest way
Let's say I have ordered NSArray
from NSNumbers
:
2, 4, 8, 15, 16, 20 // for simplicity let treat it as array of int instead of NSNumbers
Now I need to find the closest index to say 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 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 else has an idea? How can I improve the algorithm?
I looked at for example a SOF question , but it looks for a non-index value and does so by looking at all values. In the case of an index, we don't need to go through the full array.
source to share
Suppose you have an array of NSNumbers:
NSArray *array = @[@(2), @(4), @(8), @(15), @(16), @(20)];
And you are looking myValue
like below:
NSNumber *myValue = @(17);
Use the method indexOfObject:inSortedRange:options:usingComparator
to find the closest array index to you. Binary search has O (log n) performance, so it's pretty fast.
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 the number closest to yours exists myValue
in the index searchIndex - 1
:
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 are now the closest to myValue
.
Remember that yours array
must be sorted in ascending order to do this trick.
source to share