Binary Search Question

[jyurkiw]

Okay, I feel a bit like a bonehead but...

I'm studying data structures for my college advancement exam and I found something about binary searches to be quite bewildering.

In specific, I'm talking about performing a binary search on a linked list. Anyway, the first step in performing the search is to put all the (sorted) data in the list into an array to allow random access. Then you perform the binary search.

Anyway, since I have to move all the data in the list into an array in the first place, what makes the binary search more efficient than doing a linear search? If I have to step through the array anyway (if I'm understanding this correctly, the difference is 2n vs. n + log n...hardly something to cheer about unless you're dealing with massive data sets)...

I can understand that the binary search might be more efficient than the linear search when dealing with large ammounts of sorted data (like a list of size 1,000,000 or so), but is it really that much of a difference? Or is a binary search little more than a pre-requisite to implementing a selection sort?

Jeff

[googler]

In specific, I'm talking about performing a binary search on a linked list.
That's not possible.

Anyway, the first step in performing the search is to put all the (sorted) data in the list into an array to allow random access. Then you perform the binary search.

Ah, well that's a binary search on an array then, not on a linked list.

Anyway, since I have to move all the data in the list into an array in the first place, what makes the binary search more efficient than doing a linear search? If I have to step through the array anyway (if I'm understanding this correctly, the difference is 2n vs. n + log n...hardly something to cheer about unless you're dealing with massive data sets)...
Actually, it's n vs. n + log n.
It all depends how many searches you have to do. If you just have to do one or a few, there is no sense in searching like this, but if you have to do a million, it might begin to make sense.


I can understand that the binary search might be more efficient than the linear search when dealing with large ammounts of sorted data (like a list of size 1,000,000 or so), but is it really that much of a difference?

If you just have to do one search for a 1000000, it doesn't matter much. If you have to do 1000000 searches for 1000000, you'll start feeling the pain if you do linear search.

Or is a binary search little more than a pre-requisite to implementing a selection sort?
A binary search can't be used as a basis for a sort, because it requires the array to be sorted. It's very useful as an algorithm by itself.

[mehdi62b]

Binary search is applicable for indexed structures which have random access capabilities not structures like linked list.

[jyurkiw]

Yeah. I'm studying up on all the stuff I learned in my Data Structures class and their method of instruction is not unlike filling up a trash can with everything they could and just dumping it in the student's lap.

Lots of "this is how you do this", but an unfortunately small ammount of "this is why you do this".

I realise you can't use a binary search to directly search a linked list. They don't work that way.

I would use it if I wanted to perform a number of consecuative searches on sorted data for example.

Here's a bit more data to help define my question...

In class, our assignment had us implement a binary search function in a linked list class (first step: convert the list to an array; second step: perform the search). The rest of the assignment involved inserting data and performing a single binary search (demonstrating every step of the search).

I guess my problem was that we were performing a single search on a set of data rather than several so we were forced to rebuild the array every search.

That is not efficient...

I hate arbitrary assignments. They hide as much as they teach.

[googler]

In class, our assignment had us implement a binary search function in a linked list class (first step: convert the list to an array; second step: perform the search). The rest of the assignment involved inserting data and performing a single binary search (demonstrating every step of the search).
You're right, it's a dumb assignment because converting the list to an array takes more time than a single linear search of the list.