3 replies to this topic

[MasterD009]

Hey guys. I've got a question regarding binary and sequential search.

If the list has 1024 items (lg1024 = 12) at what point (the number of searches) does sorting the list first and using binary search pay off?

Sorry, was not sure if this is the correct forum.

[WingedPanther]

First: log_2(1024) = 10
That said, it depends on several factors:
Cost of sorting, frequency of searches, frequency of inserts, etc.

[MasterD009]

There isn't really anything related to the cost, frequency etc. It's a tricky question that I am having problems with.

[WingedPanther]

The answer to the question really depends on the factors I listed. The two search versions each have an overhead cost, as does sorting. The frequency with which you sort, and the cost of the sort algorithm chosen, is going to impact whether one search or another is best.

Short answer: "It depends on what all you are doing"

I've got some tutorials on doing searches, sorts, and inserts with linked lists and arrays and trees that may help answer your question.
http://forum.codecal...nked-lists.html
http://forum.codecal...rees-101-a.html