› IT & Software › IT & Software Articles › Programming Articles › Difference Between Linear Search and Binary Search
Difference Between Linear Search and Binary Search
6 mins read815 Views Comment
Vikram Singh
Assistant Manager - Content
Updated on Jun 10, 2024 11:29 IST
Uncover the distinctions between Linear and Binary Search. Linear Search, ideal for smaller datasets, examines each element sequentially. In contrast, Binary Search efficiently navigates larger, sorted datasets by halving the search interval. Choose wisely to optimize your algorithm’s performance and ensure rapid, precise outcomes in your computing tasks.
Table of Content
- Difference Between Linear Search and Binary Search: Linear Search vs Binary Search
- What is Linear Search?
- What is Binary Search?
- Key Difference Between Linear and Binary Search
Recommended online courses
Best-suited Programming courses for you
Learn Programming with these high-rated online courses
IT SparkCertificate
₹10 K
3 months
₹19.99 K
97 days
– / –
6 weeks
CMP InfotechCertificate
₹4 K
2 months
₹15 K
3 months
Merit CampusCertificate
₹2.05 K
3 months
₹31.55 K
7 months
₹26 K
3 months
Difference Between Linear and Binary Search: Linear vs Binary Search
| Parameters | Linear Search | Binary Search |
|---|---|---|
| Definition | Linear Search sequentially checks each element in the list until it finds a match or exhausts the list. | Binary Search continuously divides the sorted list, comparing the middle element with the target value. |
| Time Complexity | The time complexity is O(n), where n is the number of elements in the list. | The time complexity is O(log n), making it faster for larger datasets. |
| Efficiency | Less efficient, especially for large datasets. | More efficient, especially for large datasets. |
| Data Requirement | Does not require the list to be sorted. | Requires the list to be sorted. |
| Implementation | Easier to implement. | Requires a more complex implementation. |
| Search Space | Examines each element sequentially. | Eliminates half of the search space with each comparison. |
| Use Case | Suitable for small and unsorted datasets. | Ideal for large and sorted datasets. |
What is Linear Search?
Linear Search, also known as Sequential Search, is a straightforward method for finding a particular element within a list. It sequentially checks each element in the list until a match is found or the whole list has been searched.
- The time complexity of linear search algorithms is O(n), where n is the number of elements in the list.
- It is used for smaller datasets and the data set is unsorted.
Now, let’s understand how linear search is implemented with the help of an example.
Explore the fundamentals of data structures. Explore our top OS programmes offered by the best colleges in India and online Operating system Courses, and advance your career.
How Linear Search Works?
Use linear search algorithm in the given list: [2, 4, 6, 8, 10]. To find the number 6:
- Start from the first element (2).
- Compare the current element with the target element (6).
- If they match, the search ends.
- If they do not match, move to the next element.
- Repeat steps 2-4 until the target element is found or the list ends.
Now, its time to check how this is implemented in Python.
Problem Statement: You are given a list of integers and a target integer value. Write a Python function to search for the target value in the given list using the Linear Search algorithm. If the target value is found in the list, return the index of the value in the list; otherwise, return -1 to indicate that the value is not present in the list.
def linear_search(arr, target): """ Perform a linear search on a list to find the index of a target value.
:param arr: List of integers to search through. :param target: Integer value to search for in the list. :return: Index of the target value if found, otherwise -1. """
# Loop through each element in the list for index, element in enumerate(arr): # If the current element matches the target value, return the index if element == target: return index # Target found, return the index
# If the loop completes, the target is not in the list, return -1 return -1
# Example usage of the linear_search functionarr = [2, 4, 6, 8, 10, 12, 14]target = 8result = linear_search(arr, target)
# Output the resultif result != -1: print(f"The target {target} is found at index {result}.")else: print(f"The target {target} is not found in the list.")
Output
Explore top-rated courses for career readiness after 12th. Additionally, explore the world of specialized online degree programs for career growth.
Explanation of Example
- The linear search function takes a list (arr) and a target value as parameters.
- It iterates through each element in the list. If it finds an element that matches the target, it returns the index of that element.
- If the target is not found after checking all the elements in the list, the function returns -1.
- The example usage searches for the target value 8 in the list arr. The result is then outputted to indicate whether the target was found and at which index.
Advantage and Disadvantage of Linear Search
| Aspect | Linear Search |
|---|---|
| Advantage | Simplicity: Linear Search is straightforward and easy to implement, making it a good choice for small datasets and simple search tasks. |
| Disadvantage | Efficiency: Linear Search can be inefficient for large datasets as it checks each element sequentially, leading to a higher time complexity (O(n)) in worst-case scenarios. |
What is Binary Search?
Binary Search is a more efficient searching algorithm that finds the position of a target value within a sorted array. It compares the target value to the middle element of the array and eliminates half of the search space successively.
- The time complexity of Binary Search is O(log n), making it more efficient for large datasets.
- It is efficient for large datasets and requires sorted data.
Now, let’s understand how linear search is implemented with the help of an example.
How Binary Search Works?
Consider a sorted list of numbers: [2, 4, 6, 8, 10]. To find the number 6:
- Determine the middle element (4).
- Compare the middle element with the target element (6).
- Since 6 is greater than 4, eliminate the left half of the list.
- Repeat the process with the remaining half until the target element is found.
Now, its time to check how this is implemented in Python.
Problem Statement: You have a sorted list of integers and a target integer value. Your task is to write a Python function to search for the target value in the given sorted list using the Binary Search algorithm. If the target value is found in the list, the function should return the index of the value in the list; otherwise, it should return -1 to indicate that the value is not present in the list.
def binary_search(arr, target): """ Perform a binary search on a sorted list to find the index of a target value.
:param arr: Sorted list of integers to search through. :param target: Integer value to search for in the list. :return: Index of the target value if found, otherwise -1. """
# Initialize the left and right pointers left, right = 0, len(arr) - 1
# Continue the search while the left pointer is less than or equal to the right pointer while left <= right: # Calculate the middle index mid = (left + right) // 2
# If the middle element is the target, return the middle index if arr[mid] == target: return mid # Target found, return the middle index
# If the middle element is less than the target, search in the right half elif arr[mid] < target: left = mid + 1
# If the middle element is greater than the target, search in the left half else: right = mid - 1
# If the loop completes, the target is not in the list, return -1 return -1
# Example usage of the binary_search functionarr = [2, 4, 6, 8, 10, 12, 14]target = 10result = binary_search(arr, target)
# Output the resultif result != -1: print(f"The target {target} is found at index {result}.")else: print(f"The target {target} is not found in the list.")
output
Explanation of Example
- The binary_search function takes a sorted list (arr) and a target value as parameters.
- It uses two pointers, left and right, to represent the current search space in the list.
- It calculates the middle index and compares the middle element with the target.
- Based on the comparison, it either returns the middle index or adjusts the left and right pointers to search in the left or right half of the list.
- If the target is not found after the search space is exhausted, the function returns -1.
- The example usage searches for the target value 10 in the list arr. The result is then outputted to indicate whether the target was found and at which index.
Advantages and Disadvantages of Binary Search
| Aspect | Binary Search |
|---|---|
| Advantage | Efficiency: Binary Search is highly efficient for large datasets. It significantly reduces the search space by half with each comparison, leading to a time complexity of O(log n). |
| Disadvantage | Sorted Data Requirement: Binary Search requires the dataset to be sorted beforehand. This prerequisite can be a limitation if dealing with unsorted or dynamically changing datasets. |
Key Differences Between Linear Search and Binary Search
- Binary Search is generally more efficient than Linear Search, especially for large datasets.
- Linear Search has a time complexity of O(n), while Binary Search has a time complexity of O(log n).
- Binary Search requires sorted data, whereas Linear Search does not.
- Binary Search is more complex to implement compared to Linear Search.
- Linear Search examines each element one by one whereas binary search eliminates half of the search space with each step.
About the Author
Vikram Singh
Assistant Manager - Content
Vikram has a Postgraduate degree in Applied Mathematics, with a keen interest in Data Science and Machine Learning. He has experience of 2+ years in content creation in Mathematics, Statistics, Data Science, and Mac... Read Full Bio
Top Picks & New Arrivals
Popular Blogs
Latest Blogs
