Re: Binary searching with Perl.

Noting that this is a learning exercise and "use a hash" advice is unhelpful.

A binary search only becomes more efficient than a linear search, if the data is already sorted, or if you can sort once and amortise the cost of that sort over many, many searches.

If the data being search is static within the context of the program, then you should ensure that the program receives that data pre-sorted. If the data is dynamically aquired (gets added to) during the life of the program, then you should maintain the data in it sorted state.

Maintaining dynamic datasets in an order state means using either a binary search and insert on a linked list or maintaining the data as a binary tree

Comment on Re: Binary searching with Perl.

Replies are listed 'Best First'.
Re: Binary searching with Perl. by Abigail-II (Bishop) on May 24, 2003 at 11:47 UTC
Maintaining dynamic datasets in an order state means using either a binary search and insert on a linked list Binary search on a linked list? How would you do that efficiently? Abigail	[reply]
Re: Re: Binary searching with Perl. by Anonymous Monk on May 24, 2003 at 13:45 UTC
s/binary/linear/	[reply]
Re: Re: Binary searching with Perl. by zby (Vicar) on May 26, 2003 at 08:03 UTC
I believe it is beneficial for a learner to see the other ways of thinking. While my remark was not focused on helping the inquirer to master binary searching it was aimed at helping her to get a broader view of the subject. I don't see why do you describe it as unhelpful. The other points of you post are quite valid - but I did not write anything against them. I would just add to it that can use a tied hash to accomplish the goal of maintaining data in a binary tree, by using for example BerkeleyDB::Btree.	[reply]