File Exchange

image thumbnail

Binary Search

version 1.0.0.0 (1.55 KB) by Aroh Barjatya
Binary search of values in a data vector.

4 Downloads

Updated 20 Oct 2005

View License

bsearch(x,var)

Binary search for values specified in vector 'var' within data vector 'x'. The data has to be pre-sorted in ascending or decending order. There is no way to predict how the function will behave if there are multiple numbers with same value. Returns the index values of the searched numbers. If the values in 'var' are outside the range of 'x' then either 1 or length(x) are returned as indices for those values.

Cite As

Aroh Barjatya (2020). Binary Search (https://www.mathworks.com/matlabcentral/fileexchange/7552-binary-search), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (15)

Perfect binary search for ascending sorted arrays. Best thing is that it returns the index of the nearest number when an exact match is not found. Exactly what I was looking for. Thank you!

The function only has log(n) performance on arrays sorted in ascending order. When the order is descending, the function becomes linear, and has worse performance than find.

The function used fliplr and flipud who are terrible for the usage: we are using binary search to get log(n)-time efficiency, but both of the functions are linear.

If your algorithm is linear, we prefer ind = find(x==var) rather than your algorithm.

gromi

I use it frequently and it works fine. Thanks
1 thing to mention - the following sentence

'If the values in 'var' are outside the range of 'x' then either 1 or length(x) are returned as indices for those values.'

is not included in M-file help text (first few lines description). So if you download this function, do not use it for some time and forget about this then you may be surprised using it and getting many ones or 'x' lengths. Reading M-file description does not help in this case. You have to analyze code or go to the website.
This is a minor thing, of course.

C. Chaya

Julio

Hi
The error prevention in the beginning is rejecting the (1x1, 1x1) case. To make it work in this case one can simply add an equal ('=') sign to line 20 and it will be as below:

elseif x(1) <= x(xLen) % means x is in ascending order

Thnks

Mariano Beguerisse

I would suggest something like this to indicate that the value searched is not in the array.

if x(index) ~= var
index = 0;
end

Otherwise, works very nice

Russ S

It was off by 1.

Paresh Murthy

FYI: This code does not work in at least 1 extreme case:

the x vector is 1x1 and var is 1x1.

Seems to work otherwise. Thanks.

M Khan

in respone to comments of Aroh Barjatya that he wrote in response to my comments :) .If the value 'var' is outside the min-max limit of vector 'x' then either index = 1 or index=length(x) is returned but then the calling method may think the value is found at index=1 or last index but which is not the case. Thefore all standard implementation of binray serach return -1, if the element to be search is not found in the given array.
Anyway comments are to improve the program not to discourage. Your program is good and I appreciate it. Thanks

Aroh Barjatya

reply to comment from M.Khan: My intention while writing this function was to find the closest value 'var' within data vector 'x' and return its index. If the value 'var' is outside the min-max limit of vector 'x' then either index = 1 or index=length(x) is returned. Its a function thats written for a specific purpose of finding indices of certain values within a presorted vector. Its not a 'fool' proof function and the person who uses this better understand the limitations of its capability. If used in a proper specific way, it can speed up things quite a bit.

reply to comment from Mukhtar Ulah: For my simple purposes the 'elaborate' functions ismember and findarray were over kill.

Ji Soo Yi

I used this one. This works excellent for me. Thank you very much.

M Khan

It is good but I found following problem in this submission:

the function should return -1 if the element to be search is not in the data vector. but it does not do so.
------------------
One comment in response to comment of "Mukhtar Ulah". It is not right to compare this function with matlab built in method "ismember" becuase "ismember" first sorts the data the search, so if the data is already sorted as it is required in case of binary searach then we can skip the sorting part and "bsearch" would work mush faster then "ismember". The sorting complexity of quicksort/merge sort is nlog(n) and searching complexity of binary search is log(n). Therefore combine complexity of search+sort is larger then only binary search.

Mukhtar Ulah

Search MATLAB documentation first before writing such codes. The ML function ismember does exactly what you want here. A more elaborate function is FINDARRAY in this fiel exchange which also has a way of handling multiple instances.

Updates

1.0.0.0

update for out of bound values

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

Inspired: Binary Search for numeric vector