Binary searching versus linear searching

Linear search

In linear search, we start searching of value from start until the value is not found or end of file. If it is, then you can stop searching and report that you have found the record.

Input A[n + 1] and x.

Set i to 1.

Repeat this loop:

     If A[i] = x, then exit the loop.

     Set i to i + 1.

Return i.

Complexity: O(n).

Pros:

Serial searching is excellent if your records are unordered.

Compared to a binary search, serial searching is a very easy to implement.

Cons:

Serial searching isn’t very efficient. That's because it takes lots of comparisons to find a particular record in big files, compared to binary searching. It takes longer on average to find a record in a big file compared to binary searching.

Example: For a file of size 2^20, there are 2^20 comparisons required in worst case.

Binary search

BinarySearch(A[0..N-1], value) {

      low = 0

      high = N - 1

      while (low <= high) {

          mid = (low + high)/2

          if (A[mid] > value)

              high = mid - 1

          else if (A[mid] < value)

              low = mid + 1

          else

              return mid

      }

      return not_found

}

Complexity: O(logn).

Pros:

Compared to a linear search, binary searching is a very efficient.

Example: For a file of size 2^20, there are 20 comparisons required in worst case.

Comparisons required: log(2^20) = 20.

Cons:

Binary searching cannot be applied on the unordered array.

It is little complex to write binary search compare to linear search.