Our algorithms chapter has both linear and binary search and I need to know which is faster and when to use each one. Binary search confuses me.
Linear search checks elements one by one from the start until it finds the target or reaches the end, so it works on any list, sorted or not, but is slow for large lists. Binary search is much faster but needs the list to be sorted first. It looks at the middle element; if that is the target, done; if the target is smaller, it searches only the left half; if larger, only the right half, repeatedly halving the search space. Example: in a sorted list of 1000 items, linear search may take up to 1000 comparisons, while binary search takes at most about 10, since it halves each time. So use linear search for small or unsorted data, and binary search for large sorted data where speed matters. Binary search has time complexity O(log n) versus O(n) for linear.
Sign in as a tutor to answer this doubt.