Linear search checks elements one by one from the start; it works on any list and costs O(n) worst case. Binary search instead exploits sortedness: it checks the middle, then discards the half that cannot contain the target, halving the search space each step for O(log n) cost. The trade-off: binary search requires the data to be pre-sorted.
Binary search halving vs linear scanLinear: for i in 0..n-1: if a[i]==x return i O(n)
Binary: lo:=0, hi:=n-1
mid := (lo+hi)/2
a[mid]<x → lo:=mid+1 ; a[mid]>x → hi:=mid-1
O(log n) comparisons
Searching 8 elements: linear ≤ 8, binary ≤ 4.