Which one is run-time efficient and storage efficient in alogarithm?

Question

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

detalied explaination is really appreciated

Answer 1

@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

Answer 2

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.