Binary Search

Binary search of values in a data vector.

Description

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.

• Acknowledgements: This submission has inspired the following:; Binary Search for numeric vector
• MATLAB release: MATLAB 6.5 (R13)

[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.

[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.

[Ji Soo Yi]

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

[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.

[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

[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.

[Russ S]

It was off by 1.

[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

[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

[C. Chaya]

 

[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.

[Zhiqiang Zhang]

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.

[[e-mail]]

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.