In this Python tutorial, we will discuss, linear search and binary search in Python program. This tutorial will walk you through implementing two of the most fundamental search algorithms: linear search and binary search in Python. You will also learn to implement binary search without using functions.
linear search and binary search in Python
Searching is a common operation in computer science, where you need to find a particular value from a collection of values. Two common algorithms for this operation are linear search and binary search.
Linear Search:
- In linear search, you start from the first element and compare each element with the target value until you find a match.
- Time Complexity: O(n)
How it works:
- Start from the first element of the array.
- Compare the target value with the current element.
- If it matches, return the index.
- If not, move to the next element.
- Repeat steps 2-4 until you find the target or reach the end of the array.
Performance:
- Time complexity is O(n) because, in the worst-case scenario, it checks each element in the array.
- No requirement for the array to be sorted.
Binary Search:
- In binary search, the array must be sorted. You repeatedly divide the array into halves until the value is found.
- Time Complexity: O(log n)
How it works:
- The array must be sorted before using binary search.
- Start by setting two pointers, one at the start (left) and one at the end (right) of the array.
- Find the middle element.
- Compare the middle element with the target.
- If it matches, return the index.
- If the target is larger than the middle element, move the left pointer to the middle + 1.
- If the target is smaller than the middle element, move the right pointer to the middle – 1.
- Repeat steps 3-7 until you find the target or the pointers cross (left > right).
Performance:
- Time complexity is O(log n) because it effectively halves the search space with each iteration.
- Requires the array to be sorted.
Linear Search in Python
Implementing Linear Search
Here’s a step-by-step guide to implementing a linear search algorithm in Python:
def linear_search(arr, target):
# Loop through each element in the array
for index, element in enumerate(arr):
# If the element matches the target, return the index
if element == target:
return index
# If the loop finishes, the target was not found
return -1
Example: Linear Search Program in Python
Let’s write a Python program for linear search to find the index of a target value in an array.
def linear_search(arr, target):
for index, element in enumerate(arr):
if element == target:
return index
return -1
# Example array and target value
arr = [4, 2, 7, 1, 9, 3]
target = 7
# Call the linear_search function
index = linear_search(arr, target)
# Output the result
if index != -1:
print(f"Element {target} found at index {index}")
else:
print(f"Element {target} not found in the array")
You can see the output:
Binary Search in Python
Implementing Binary Search with a Function
Here’s a step-by-step guide to implementing binary search using a function:
def binary_search(arr, target):
left, right = 0, len(arr) - 1
# Continue the search while the left index is less than or equal to the right index
while left <= right:
mid = (left + right) // 2
# Check if the target is present at mid
if arr[mid] == target:
return mid
# If target is greater, ignore the left half
elif arr[mid] < target:
left = mid + 1
# If target is smaller, ignore the right half
else:
right = mid - 1
# If we reach here, the element was not present
return -1
Example: Binary Search Program in Python
Let’s see a Python program to implement binary search using the above function.
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# Example sorted array and target value
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 6
# Call the binary_search function
index = binary_search(arr, target)
# Output the result
if index != -1:
print(f"Element {target} found at index {index}")
else:
print(f"Element {target} not found in the array")
You can see the output like below:
Implement Binary Search Without a Function
Here’s how you can write a Python program to implement binary search without using a function.
Example: Binary Search in Python Without a Function
# Example sorted array and target value
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 6
# Set initial left and right indices
left, right = 0, len(arr) - 1
# Binary search without function
while left <= right:
mid = (left + right) // 2
# Check if target is present at mid
if arr[mid] == target:
print(f"Element {target} found at index {mid}")
break
# If target is greater, ignore the left half
elif arr[mid] < target:
left = mid + 1
# If target is smaller, ignore the right half
else:
right = mid - 1
else:
print(f"Element {target} not found in the array")
You can see the output below in the screenshot.
Linear Search and Binary Search in Python
Here is a comparison of Linear Search and Binary Search in Python in a tabular format:
Aspect | Linear Search | Binary Search |
---|---|---|
Algorithm Type | Sequential Search | Interval Search |
How it works | Sequentially checks each element for a match | Repeatedly divides the search interval in half |
Sorted Data Required | No, works on both sorted and unsorted arrays | Yes, only works on sorted arrays |
Time Complexity | O(n) | O(log n) |
Space Complexity | O(1) | O(1) |
Implementation | Easier | Slightly more complex |
Performance | Slower for large datasets | Faster for large datasets |
Best-case Scenario | O(1), when the element is at the first position | O(1), when the element is at the middle position |
Worst-case Scenario | O(n), when the element is at the last position or not present | O(log n) |
Use Cases | Small datasets, unsorted data | Large datasets, sorted data |
This table summarizes the key differences between linear search and binary search algorithms in Python.
Conclusion
This tutorial has covered how to implement linear search and binary search in Python, including examples with and without using functions. Whether you’re looking to write a python program to implement linear search and binary search, or specifically focusing on binary search in Python without using a function, this tutorial has you covered.
You may also like:
- Fastest sorting algorithm in Python
- raw input function in Python
- get values from json array in Python
- Add two binary numbers in Python
I am Bijay Kumar, a Microsoft MVP in SharePoint. Apart from SharePoint, I started working on Python, Machine learning, and artificial intelligence for the last 5 years. During this time I got expertise in various Python libraries also like Tkinter, Pandas, NumPy, Turtle, Django, Matplotlib, Tensorflow, Scipy, Scikit-Learn, etc… for various clients in the United States, Canada, the United Kingdom, Australia, New Zealand, etc. Check out my profile.