image thumbnail

Binary search for closest value in an array

version 1.0.0.0 (1.43 KB) by Benjamin Bernard
Returns closest value and corresponding index in an increasingly ordered array.

320 Downloads

Updated 27 Aug 2012

View License

Input values
============
arr : increasingly ordered array of values in R
val : scalar in R

Description
===========
Returns the value and index of 'arr' that is closest to 'val'. If several entries are equally close, the first one is returned.

Limitations
===========
Works fine up to machine error, e.g. [v, i] = closest_value([4.8, 5], 4.9) will return [5, 2], since in float representation 4.9 is strictly closer to 5 than to 4.8. See also http://en.wikipedia.org/wiki/Floating_point

Purpose
=======
Why upload another binary search? I found that many uploaded files are unnecessarily complicated and either don’t have a predetermined outcome (f.ex. the first one) if there are several choices or crash if the value to be searched for lies outside the boundaries of the array. Also, this code is thought to be instructional for people new to Matlab to build their own binary searches on. That’s why I kept it to the simplest case where the array needs to be increasingly ordered and the first of several values is returned. The code could be easily adapted for returning the last index instead, to allow for decreasingly ordered arrays, for fractional indices or for other well-ordered spaces. If you are looking for an implementation in C that allows for all these behaviour modifications, here is a very nice one: http://www.mathworks.com/matlabcentral/fileexchange/30484-fast-binary-search

Cite As

Benjamin Bernard (2021). Binary search for closest value in an array (https://www.mathworks.com/matlabcentral/fileexchange/37915-binary-search-for-closest-value-in-an-array), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2011b
Compatible with any release
Platform Compatibility
Windows macOS Linux
Acknowledgements

Inspired: fast_sorted_mask, fast_search_histogram

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!