bsearch is pretty good for direct search, but what should I use if I need for example search range?
update
for example if i want to find range of values between a and b ( a >= x < b ).
开发者_运维知识库update
range values can be not equal. so if i have array(10,20,30) and i'm trying to find "15" i want to get address (pointer) to minimal range that is closest, in this example this is range (10,20)
One of the parameters bsearch
takes is the number of elements to search. So instead of, for example, 100, make it search in 42 ...
bsearch("foo", data, /*100*/42, sizeof *data, cmpfx);
After the update
What I'd do is a manual (meaning I'd write the code) binary search.
The idea is to compare the middle element of the (remaining) array to both the lower and upper limit. If it's smaller then the lower limit search again in the small half; if it's larger than the upper limit search again in the big half; otherwise you've found an element in range.
After the 2nd update
You want to return a pair of pointers?
You have to wrap them inside a struct, or pass the addresses of the pointers to the functions ... or something.
But now you have a simpler search: search until you find the value (and return a 0-length range) or until you are about to fail. The range is between the array value you last looked at and, depending on exactly how you got to the fail situation, the value to one of the sides or EMPTY if you're at the end of the array.
The bsearch()
function is designed to find a single element matching some condition. According to the man page:
RETURN VALUE
The bsearch() function returns a pointer to a matching member of the
array, or NULL if no match is found. If there are multiple elements
that match the key, the element returned is unspecified.
The key here is that if there are multiple elements that match the key, the element returned is unspecified. So you don't know if the element you get is the first, last, or somewhere in the middle of the range.
If you can change your requirements so that you're looking for elements in the array between A and B, and you can guarantee that there is exactly one A and exactly one B in the array, then you could first search for A then search for B.
start = bsearch(A, array, N, sizeof(*array), compare);
end = bsearch(B, array, N, sizeof(*array), compare);
You'll probably have to write your own function to do exactly what you're wanting.
精彩评论