-1

I'm confused whether linear search or binary search is more efficient in running time and storing.

detalied explaination is really appreciated

Thomas Jung
  • 32,428
  • 9
  • 84
  • 114
Erika Sawajiri
  • 1,136
  • 3
  • 13
  • 18
  • of course binary search is more efficient if the list is already sorted as it is an `O(log N)` algorithm while linear search takes `O(N)` for both sorted and unsorted data. For sorted data use binary search, for unsorted data use linear search. – Ashwini Chaudhary Jun 24 '13 at 06:56
  • Related posts : [what does O(N) mean](http://stackoverflow.com/questions/1909307/what-does-on-mean), [What does O(log n) mean exactly?](http://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly) – Ashwini Chaudhary Jun 24 '13 at 07:00
  • 2
    If you would have spent a couple minutes before posting to read the first few sentences of the relevant Wikipedia articles ([linear](http://en.wikipedia.org/wiki/Linear_search), [binary](http://en.wikipedia.org/wiki/Binary_search)) you would have seen this: _... Therefore, if the list has more than a few elements, other methods (such as **binary search or hashing) will be faster**, but they also impose additional requirements._ – DaoWen Jun 24 '13 at 07:09
  • @Erika This is not something you should ask.Have you even read what these two are?Because if you have you would not ask it.Please show some effort before asking a question. – Aravind Jun 24 '13 at 08:05

2 Answers2

3

A linear search starts at the beginning and compares every element until it finds what you're looking for.

A binary search splits the list in the middle and looks if your value is greater or smaller than the pivot value. Then it continues doing so recursively.

For example in a list of people. You're looking for John. The binary search looks in the middle of the list and might find Mark. John is lower, so the search discards the upper half of the list, since John will not be in it, and repeats this on the lower half (recursion)

A binary search is much more efficient but the list must be sorted.

However - sorting a list is slower than a linear search. You won't win in efficiency by sorting a unsorted list first.

Christoffer
  • 7,470
  • 9
  • 39
  • 55
  • 2
    Depends on how many times you will search the list, if that was always true no one would ever sort a list. – Jake Sellers Jun 24 '13 at 07:06
  • @Jake Sellers: Yes, good point. An address book is a good example. You're probably going to search a lot more often than you're adding new people. – Christoffer Jun 24 '13 at 07:08
3

@Trophe covered the time complexity, so I'll try to explain the space complexity

The space requirement has the same complexity

a linear search is simpler and needs just one variable

a binary search needs to store a lower and upper bound, so it's more space, but it's not dependent on the size of the list

So we say they are both O(1) space complexity

John La Rooy
  • 295,403
  • 53
  • 369
  • 502