Linear search vs. Binary search

Linear search

• Complexity : O(n)
• Suited for unordered array
• Loop starts from first element till the item found or end of the array.
• In Worst case, it will take 2^20 comparisons for 2^20 records.
• Easy to implement
• Takes longer time (in average) to find an item than Binary search

for (int i=0; i<array.length(); i++) {
  if (array[i] == value) {
       return i;  // item found, return the index
  }
}

return -1;  // Not found


Binary search

• Complexity : O(log n)
• Very efficient than Linear search
• Only applied on ordered array ; cannot be applied on unordered array
• Little complex algorithm than Linear search
• In Worst case, it will take only 20 comparisons for 2^20 records.

int low = 0;

int high = len - 1;

while (low <= high) {

   mid = (low+high) / 2;   // Find the mid index

   
   if (array[mid] == value)
        return mid;       // Found, return mid index

   else if (array[mid] > value)  // If value is lesser than mid element

        high = mid - 1;   // Search before mid - Adjust 'high'

   else if (array[mid] < value)  // If value is greater than mid element

        low = mid + 1;    // Search after mid - Adjust 'low'

}

return -1;  // Not found