Linear Search vs Binary Search: Key Differences Explained Simply

Search algorithms in data structure is a core concept in programming that helps locate an element within a dataset. As developers, being aware of which search algorithm to use can significantly impact the efficiency of our programs. Two popular search methods are linear search and binary search, each suited to different use cases. The difference between linear search and binary search lies in their approach and performance.

Linear search is simple and checks each element one by one until it finds the desired item or reaches the end of the list. Binary search, however, is faster but works only on sorted datasets by repeatedly dividing the search range into halves.

In this blog, we’ll explore the difference between linear search and binary search in detail, discuss their time complexities, and learn when to use each method.

To fully grasp these concepts, it’s important to have a solid foundation in data structures. This guide walks you through the essentials.

What is a Linear Search?

Linear search, also known as sequential search, is one of the simplest algorithms used to find the position of a target element in a list or array. It works by scanning each element one by one, starting from the first index, until the desired element is found or the list ends. This algorithm is suitable for both sorted and unsorted data.

How Linear Search Works

1. Begin at the first element of the array or list.
2. Compare each element with the target value.
3. If a match is found, return the position of the element.
4. If the end of the list is reached without finding a match, return -1.

Linear search does not skip elements and ensures that all possible matches are checked. However, it can be inefficient for large datasets due to its O(n) time complexity in the worst case.

Begin Search at Index 0: Start from the first element (arr[0] = 10).

• Compare 10 with 5. No match, move to the next index.

Continue Sequential Comparisons:

• arr[1] = 8: No match.
• arr[2] = 1: No match.
• arr[3] = 21: No match.
• arr[4] = 7: No match.
• arr[5] = 32: No match.

Find Match at Index 6:

• At arr[6] = 5, the search key matches the element in the array.
• Stop the search process immediately.

Result:

• The element 5 is found at index 6.
• Return the index position 6 as the result.

You might also find this helpful: A free Python course that comes with certification.

What is Binary Search?

Binary search is an efficient search algorithm that repeatedly divides a sorted dataset into halves to find the position of a target element. Unlike linear search, which checks each element sequentially, binary search narrows down the search area by comparing the target with the middle element of the dataset. This approach significantly reduces the number of comparisons, making it faster and more suitable for large datasets, provided they are sorted.

How Binary Search Works

Binary search operates on the divide and conquer principle. Here's the step-by-step explanation:

1. Start by comparing the target element with the middle element of the sorted array.
2. If the target matches the middle element, the search ends successfully.
3. If the target is smaller than the middle element, search in the left half of the array.
4. If the target is larger than the middle element, search in the right half of the array.
5. Repeat the process until the target is found or the search space is exhausted.

Start the Search:

• Begin with the entire sorted array {10, 14, 19, 26, 27, 31, 33, 35, 42, 44}.
• Initial Range: Set low = 0 (start of the array) and high = 9 (end of the array).

First Comparison:

• Calculate Middle Index: mid = (low + high) / 2 = (0 + 9) / 2 = 4.
• Check Middle Element: arr[4] = 27.
• Compare with Target (33):
  • 33 > 27 → Target is in the right sub-array.
  • Update Range: Set low = mid + 1 = 5.

Second Comparison:

• Recalculate Middle Index: mid = (low + high) / 2 = (5 + 9) / 2 = 7.
• Check Middle Element: arr[7] = 33.
• Compare with Target (33):
  • 33 == 33 → Target found at index 7.
  • Stop Search: Return index 7.

Differences Between Linear Search and Binary Search

Linear search and binary search are two fundamental search algorithms with distinct approaches, data requirements, and efficiency levels. Here's a breakdown of their differences:

Advantages and Disadvantages of Linear and Binary Search

Time Complexity of Linear Search

Linear search is a straightforward algorithm that examines each element in a list one by one to find a target value. As the size of the dataset increases, the time required to find the target also increases proportionally. Here’s a detailed look at its complexity:

Complexity Analysis of Linear Search

1. Best Case: O(1)
   • The search is successful in the first comparison.
   • Example: The target element is at index 0.
2. Worst Case: O(n)
   • The search iterates through the entire list.
   • Example: The target is at the last index or absent in the dataset.
3. Average Case: O(n)
   • On average, the search will find the element somewhere in the middle of the list. It will perform n/2 comparisons but is represented as O(n) for asymptotic analysis.
4. Space Complexity: O(1)
   • Linear search operates directly on the input array without requiring additional memory, making it space-efficient.

Example to Illustrate Complexity

Find the number 13 in the array {1, 3, 5, 7, 9, 11, 13} using linear search.

Code Example:

java

public class LinearSearchDemo {
    public static int linearSearch(int[] array, int target) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == target) {
                return i; // Target found
            }
        }
        return -1; // Target not found
    }

    public static void main(String[] args) {
        int[] numbers = {1, 3, 5, 7, 9, 11, 13};
        int target = 13;
        int result = linearSearch(numbers, target);

        if (result == -1) {
            System.out.println("Element not found.");
        } else {
            System.out.println("Element found at index: " + result);
        }
    }
}

Output:

mathematica

Element found at index: 6

The output indicates that the target element (13) was successfully located in the array at index 6. 

Linear Search Algorithm: Steps and Syntax

Linear search is a straightforward algorithm for finding an element in a list. It works by sequentially checking each element until the target is found or the list ends.

Steps of the Linear Search Algorithm

1. Start at the First Element:

   Compare the target value with the first element in the array.

2. Sequential Comparison:

   If the first element is not the target, move to the next element and compare.

3. Repeat Until Found or End:

   Continue this process until the target element is found or the end of the list is reached.

4. Return the Result:
   • If the element is found, return its index.
   • If not, return -1 to indicate that the element is not present.

Code Examples in Different Languages

1. C++: Linear Search Syntax

The program searches for the target 30 in the array {10, 20, 30, 40, 50}.

cpp

#include <iostream>
using namespace std;

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i; // Element found, return index
        }
    }
    return -1; // Element not found
}

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 30;
    
    int result = linearSearch(arr, n, target);
    if (result == -1) {
        cout << "Element not found." << endl;
    } else {
        cout << "Element found at index: " << result << endl;
    }
    return 0;
}

Output:

mathematica

Element found at index: 2

2. Java: Linear Search Syntax

The program searches for the target 15 in the array {5, 10, 15, 20, 25}.

java

public class LinearSearch {
    public static int linearSearch(int[] array, int target) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == target) {
                return i; // Return index of the target
            }
        }
        return -1; // Element not found
    }

    public static void main(String[] args) {
        int[] arr = {5, 10, 15, 20, 25};
        int target = 15;
        int result = linearSearch(arr, target);
        
        if (result == -1) {
            System.out.println("Element not found.");
        } else {
            System.out.println("Element found at index: " + result);
        }
    }
}

Output:

mathematica

Element found at index: 2

3. Python: Linear Search Syntax

The program searches for the target 6 in the array [2, 4, 6, 8, 10].

python

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # Return index of the target
    return -1  # Element not found

# Main program
arr = [2, 4, 6, 8, 10]
target = 6

result = linear_search(arr, target)
if result == -1:
    print("Element not found.")
else:
    print(f"Element found at index: {result}")

Output:

mathematica

Element found at index: 2

Example: Searching an Element in an Array

Find the position of a target number, 13, in the unsorted integer array {10, 23, 45, 13, 67, 89, 13, 99} using linear search.

java

public class LinearSearchExample {
    // Linear search method
    public static int linearSearch(int[] array, int target) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == target) {
                return i; // Return the index if the target is found
            }
        }
        return -1; // Return -1 if the target is not found
    }

    public static void main(String[] args) {
        // Array of integers
        int[] numbers = {10, 23, 45, 13, 67, 89, 13, 99};
        int target = 13; // Element to search
        int position = linearSearch(numbers, target);

        // Output results
        if (position == -1) {
            System.out.println("Element not found.");
        } else {
            System.out.println("Element found at index: " + position);
        }
    }
}

Output

mathematica

Element found at index: 3

Time Complexity of Binary Search

Binary search is known for its efficiency in handling large datasets due to its divide-and-conquer approach. The algorithm significantly reduces the search space by half with each step, which it faster than linear search for sorted data. Let’s see the time and space complexity analysis:

Time Complexity Analysis

• Best Case: O(1)
  • The search is completed in one step when the target element is the middle element of the array.
  • Example: In the sorted array [10, 20, 30, 40, 50], searching for 30 directly matches the middle element.
• Worst Case: O(log n)
  • The dataset is halved repeatedly until the target is found or the search space is exhausted.
  • Example: Searching for 5 or 60 in [10, 20, 30, 40, 50] requires dividing the array multiple times.

Space Complexity Analysis

• Iterative Version: O(1)
  • No extra memory is required as the algorithm uses a fixed number of variables for tracking pointers (low, high, and mid).
• Recursive Version: O(log n)
  • Additional memory is consumed due to recursive function calls, as each call adds to the stack.

Binary Search Algorithm: Steps and Syntax

Binary search is an efficient search algorithm for sorted arrays. It divides the search space in half during each step, significantly reducing the number of comparisons required.

Steps to Perform Binary Search

1. Initialize Pointers:
   • Start with two pointers: low (beginning of the array) and high (end of the array).
2. Calculate the Midpoint:
   • Compute the middle index as mid = (low + high) / 2 (or equivalent for integer division).
3. Compare the Middle Element:
   • If array[mid] == target: Return mid (target found).
   • If array[mid] < target: Shift the low pointer to mid + 1 (search in the right half).
   • If array[mid] > target: Shift the high pointer to mid - 1 (search in the left half).
4. Repeat:
   • Continue dividing and searching until the target is found or low > high.
5. Result:
   • If the target is not found, return -1.

Code Examples in Different Languages

1. C++: Binary Search Syntax

The program searches for the target 30 in the sorted array {10, 20, 30, 40, 50}.

cpp

#include <iostream>
using namespace std;

int binarySearch(int arr[], int size, int target) {
    int low = 0, high = size - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2; // Calculate mid-point
        if (arr[mid] == target) {
            return mid; // Target found
        } else if (arr[mid] < target) {
            low = mid + 1; // Search right half
        } else {
            high = mid - 1; // Search left half
        }
    }
    return -1; // Target not found
}

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 30;

    int result = binarySearch(arr, size, target);
    if (result == -1) {
        cout << "Element not found." << endl;
    } else {
        cout << "Element found at index: " << result << endl;
    }

    return 0;
}

Output:

mathematica

Element found at index: 2

2. Java: Binary Search Syntax

The program searches for the target 40 in the sorted array {10, 20, 30, 40, 50}.

java

public class BinarySearchExample {
    public static int binarySearch(int[] array, int target) {
        int low = 0, high = array.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2; // Calculate mid-point
            if (array[mid] == target) {
                return mid; // Target found
            } else if (array[mid] < target) {
                low = mid + 1; // Search right half
            } else {
                high = mid - 1; // Search left half
            }
        }
        return -1; // Target not found
    }

    public static void main(String[] args) {
        int[] numbers = {10, 20, 30, 40, 50};
        int target = 40;

        int result = binarySearch(numbers, target);
        if (result == -1) {
            System.out.println("Element not found.");
        } else {
            System.out.println("Element found at index: " + result);
        }
    }
}

Output:

mathematica

Element found at index: 3

upGrad’s Exclusive Data Science Webinar for you –

The Future of Consumer Data in an Open Data Economy

3. Python: Binary Search Syntax

The program searches for the target 50 in the sorted array [10, 20, 30, 40, 50].

python

def binary_search(arr, target):
    low, high = 0, len(arr) - 1

    while low <= high:
        mid = (low + high) // 2  # Calculate mid-point
        if arr[mid] == target:
            return mid  # Target found
        elif arr[mid] < target:
            low = mid + 1  # Search right half
        else:
            high = mid - 1  # Search left half

    return -1  # Target not found

# Example usage
arr = [10, 20, 30, 40, 50]
target = 50

result = binary_search(arr, target)
if result == -1:
    print("Element not found.")
else:
    print(f"Element found at index: {result}")

Output:

mathematica

Element found at index: 4

Example in Practice: Binary Search for Finding a Product ID

Search for the product ID 67 in the sorted array {12, 24, 35, 47, 56, 67, 78, 89} using binary search.

Code Example:

java

public class ProductSearch {
    public static int binarySearch(int[] productIDs, int target) {
        int low = 0, high = productIDs.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2; // Calculate mid-point
            if (productIDs[mid] == target) {
                return mid; // Target found
            } else if (productIDs[mid] < target) {
                low = mid + 1; // Search right half
            } else {
                high = mid - 1; // Search left half
            }
        }
        return -1; // Target not found
    }

    public static void main(String[] args) {
        int[] productIDs = {12, 24, 35, 47, 56, 67, 78, 89};
        int target = 67;

        int result = binarySearch(productIDs, target);
        if (result == -1) {
            System.out.println("Product ID not found.");
        } else {
            System.out.println("Product ID found at index: " + result);
        }
    }
}

Output:

mathematica

Product ID found at index: 5

Binary Search Example: Finding the Grade of a Student

Search for a specific grade (85) in a sorted array of grades {50, 60, 70, 80, 85, 90, 95, 100} using binary search.

Code Example:

java

public class GradeSearch {
    public static int binarySearch(int[] grades, int target) {
        int low = 0, high = grades.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2; // Calculate mid-point
            if (grades[mid] == target) {
                return mid; // Target found
            } else if (grades[mid] < target) {
                low = mid + 1; // Search the right half
            } else {
                high = mid - 1; // Search the left half
            }
        }
        return -1; // Target not found
    }

    public static void main(String[] args) {
        int[] grades = {50, 60, 70, 80, 85, 90, 95, 100};
        int target = 85;

        int result = binarySearch(grades, target);
        if (result == -1) {
            System.out.println("Grade not found.");
        } else {
            System.out.println("Grade found at index: " + result);
        }
    }
}

Output:

perl

Grade found at index: 4

Use Cases: When to Use Linear Search vs Binary Search

When to Use Linear Search

Linear search is best suited for situations where simplicity and flexibility are more important than speed.

• Unsorted Data:

  Linear search works well when the dataset is unsorted or dynamic. For example, searching for a specific customer ID in a temporary list of 20 records is more practical with linear search since no sorting is required.

• Small Datasets:

  For small datasets (e.g., fewer than 50 elements), the overhead of sorting for binary search outweighs the simplicity of linear search. For example, finding a missing item in a grocery list of 15 products.

• Checking Specific Conditions:

  Linear search is ideal for conditions like finding the first occurrence of an element satisfying a condition. For example, identifying the first even number in an array of 10 integers: {3, 7, 10, 15, 18}.

• Dynamic or Frequently Changing Data:

  If the dataset changes frequently and sorting it after every modification is impractical, linear search is the go-to solution.

• Data Structures:

  Suitable for linked lists or unsorted arrays where accessing elements by index is not straightforward.

Example: Searching for the number 5 in an unsorted list of 100 elements. Linear search will scan each element sequentially, taking up to 100 comparisons in the worst case.

When to Use Binary Search

Binary search is the algorithm of choice for large datasets where performance is critical and the data is sorted.

• Sorted Data:

  Binary search is highly efficient when working with pre-sorted datasets. For example, it can be used to find a specific book in a library catalog sorted alphabetically by title.

• Large Datasets:

  Binary search significantly reduces search time for datasets larger than 1,000 elements. For example, searching for a product ID in a database with 10,000 entries requires a maximum of only 14 comparisons (214=16,3842^{14} = 16,384214=16,384).

• Static Data:

  Ideal for scenarios where data does not change frequently. Sorting can be done once, and binary search can be applied repeatedly. Example: Searching in historical weather data.

• Applications in Databases:

  Binary search is used in databases for index-based retrieval. For example, finding a customer record in a sorted database with millions of entries can be done in logarithmic time.

• Efficient Search Needs:

  This product works well for applications that require frequent search operations, such as autocomplete suggestions in search engines or user ID lookups in authentication systems.

Example: Searching for a student’s roll number in a sorted list of 10,000 students. Binary search will require 14 steps, compared to up to 10,000 for linear search.

Explore upGrad’s Data Science Courses

Build a strong foundation in data science with upGrad’s programs designed for real-world application. 

Learn key topics like search algorithms, data structures, and analytics through practical projects. 

These courses, created with leading universities, cover data science, machine learning, and AI.

Why Choose upGrad?

• Curriculum includes the latest AI advancements.
• Hands-on training with cutting-edge tools.
• Alumni report an average 57% salary increase.
• Access 1:1 mentorship and exclusive job opportunities.

Start your journey today and gain skills that make you stand out in the data-driven world.

Start your career in tech with software development courses from top universities.

Learn from the best with our Popular Data Science Courses and become a sought-after data professional.

Unlock expert insights with our Popular Data Science Articles, covering the latest trends and techniques. From analytics to innovation, we’ve got you covered!

Boost your career prospects with the Top Data Science Skills to Learn, essential for navigating the future of analytics and AI!