binary vs linear search and arrays

Hi,

what are diferences, advantages, disadvantage, practical use, application of binary vs linear search. how they vary with respect to ordered/un ordered collections like arrays. any sample code, links resource highly appreciated. please advise
LVL 7
gudii9Asked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

dpearsonCommented:
Linear search is super simple - you go through a list of value until you find the matching one.  As a result, on average you have to check half of the values in the list.

Binary search works on an ordered list e.g. you have -3,0,2,3,5,6,8,9,10,11,12.

If you're trying to see if 9 is in the list you do the search by checking the middle value: 6.
Since 9 is bigger than 6, you search the top half of the list: 8,9,10,11,12 by checking the middle of that list which is 10.
Since 9 is less than 10 you search the lower half: 8,9
And you find the value is present.

You can hopefully see that binary search doesn't have to check every value in the list.
In fact the savings in big list can be huge - on average it will take log(n) checks - which for a list of 1024 values means only 10 checks, compared to 512 for the linear search.

Hope that helps,

Doug
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
zzynxSr. Software engineerCommented:
Some additional information:
while binary searching an ordered list is indeed faster then linear searching a unordered list, you have to realize that somewhere you "pay" for that. (no free lunch)
While adding an element to an unorder list is just adding it at the end, in an ordered list it has to be inserted at the right place in the list. Determining that right place (which is performing a linear search again) is an extra "cost" in comparison with just adding it at the end. But the more you have to search your list for items, the more that extra cost pays off.
0
zzynxSr. Software engineerCommented:
Thanx 4 axxepting
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Java EE

From novice to tech pro — start learning today.