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?

# | User | Rating |
---|---|---|

1 | Benq | 3797 |

2 | tourist | 3723 |

3 | Radewoosh | 3720 |

4 | ecnerwala | 3579 |

5 | ksun48 | 3463 |

6 | Um_nik | 3457 |

7 | maroonrk | 3446 |

8 | jiangly | 3432 |

9 | Petr | 3370 |

10 | scott_wu | 3350 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 208 |

2 | awoo | 184 |

2 | rng_58 | 184 |

4 | Errichto | 182 |

5 | SecondThread | 177 |

6 | maroonrk | 176 |

6 | Radewoosh | 176 |

6 | -is-this-fft- | 176 |

9 | Um_nik | 173 |

10 | antontrygubO_o | 169 |

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?

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/22/2021 09:00:44 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

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)$$$.