Sirandrew2's blog

How binary search is faster than linear search?
By Sirandrew2, history, 4 years ago, In English

We need a sorted array to perform a binary search in that case the time complexity already became greater than the linear search, so isnt linear search a better option in that case?

  • Vote: I like it
  • +13
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Consider having Q Queries. Binary search complexity is O(NlogN + QlogN), but normal linear search is O(QN), a pretty big difference.

→ Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

If you only have one search, then linear search would be faster. But if you're doing a bunch of searches, then you can sort the array once and do each of the searches in $$$O(\log n)$$$.

→ Reply