Binary search for closest value in an array

Returns closest value and corresponding index in an increasingly ordered array.
374 Downloads
Updated Mon, 27 Aug 2012 14:25:35 +0000

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 (2024). 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
Categories
Find more on Matrices and Arrays in Help Center and MATLAB Answers
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!
Version Published Release Notes
1.0.0.0