CODEWITHSUNDEEP
algorithmsearch
user976027
user976027

Reputation: 13

Linear Search or Binary Search or Binary Search Tree

I have a small doubt here...

If I know that a search element in a list ,say containing 32 elements sorted in order, is appearing within first four positions,

which is the best searching algorithm.

Linear search at least needs 4 iteration.... Binary search at least 5 iteration How about binary search tree .. does it give better solution in this case or is equal to binary search...

I believe Linear search will be better for such circumstances ..

can anybody confirm this please ?

Upvotes: 0

Views: 1228

Answers (4)

malejpavouk
malejpavouk

Reputation: 4445

If the data are somehow uniformly distributed, it is wise to use interpolation search. By using the knowledge of distribution, you have a good chance to guess the correct position in one step. The expected complexity is O(log(log(n))) .

Here is a link to my pages, where I have the algorithm implemented in Java: Algoritmy.net - interpolation search implementation

Upvotes: 0

Shamim Hafiz - MSFT
Shamim Hafiz - MSFT

Reputation: 22064

With exactly that number of elements and the exact application you have at hand, a Binary-Search Tree would be an overkill.

Also, for solving the problem as it stands now, Linear Search would be better as the expected number of iterations to locate a particular element will outweigh Binary Search.

For real life scenario, the problem presented as it is will be very rare. Therefore, it's always better to use Binary Search on sorted arrays.

Upvotes: 0

Aliza
Aliza

Reputation: 744

you can do a binary search on the first 4 elements. it will be lg 4 = 2 iterations! :-)

Upvotes: 0

spatulamania
spatulamania

Reputation: 6663

If you know the location is in the first 4 positions than a linear search is better since you'll have to test no more than 4 elements. With a binary search lg 32 = 5 so you'll have to test at most 5 elements.

In addition, for a small amount of elements like this, the time difference is negligible and you'll be best served by keeping it simple and doing a linear search.

You may also be able to use a HashTable or HashSet for O(1) time but then again, for a small amount of data, a linear search would probably be faster than executing a hash function.

And if the small difference really does matter, I would suggest measuring it in the environment where it will run.

Upvotes: 1

Related Questions