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?
 
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
 
zzynxSoftware 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
 
zzynxSoftware engineerCommented:
Thanx 4 axxepting
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.