Binary search on a sorted Array

[srdja]

You should be able do perform a binary search on a sorted array.

[Nekel-Seyew]

So this begs the question, when do we know it's sorted? We could sort it every time the method is called. But probably, we'd want to have a variable in array_c called "is_sorted" that is only ever set to true when the array_sort() is called, and set to false when any alteration to the array is made, yeah?

[srdja]

Yeah, sorting on each search is way worse that just doing a linear search. We definetly want to just mark the array when it's sorted.

I think it's best to implement bsearch as an internal optimization instead of a function that the user can call. For example if the user calls something like array_index_of, it can use bsearch internally if the array is marked as sorted instead of a linear search to speed up the search.

[Nekel-Seyew]

Bsearch won't work in that instance, because bsearch only returns if a given item is in the array, not the first index as "index_of" normally returns. We could then just go backwards till we get first item, but then that's basically the same as linear search.

[srdja]

There's no need to use the libc bsearch. It's trivial to implement a bsearch to return the index of the matching element.

[Nekel-Seyew]

I mean the bsearch algorithm, not just the libc implementation, isn't guaranteed to return the first element in a sorted array which matches, just returns true if it does find it. Which means we'd then have to search for it ourselves, going backwards.

[srdja]

I see what you mean. It doesn't match the spec of finding the first match in the sequence. But we should still be able to get better performance if we mix bsearch and linear search than with plain linear search, because on average, once we find the match through bsearch, we won't have to go too far backwards to find the first element.

[nimitbhardwaj]

This idea is good, but there is only problem, we need a comparator, as i saw the array implementation, the pointer to the comparator function is not stored in the array struct, so it could be easy if there was a pointer, as if the array was sorted then we could determine if the new element when added will result the array to remain sorted or not in O(1) time, and it would be easy to do bin search, in the function array_index_of function, as bin search will req a comparator, and it would not be wise to give the comparator every time in array_index_of function while searching