- linear search and binary search in Python program
- linear search and binary search in Python
- Linear Search:
- Binary Search:
- Linear Search in Python
- Implementing Linear Search
- Example: Linear Search Program in Python
- Binary Search in Python
- Implementing Binary Search with a Function
- Implement Binary Search Without a Function
- Example: Binary Search in Python Without a Function
- Linear Search and Binary Search in Python
- Conclusion
- Binary Search in Python
- Recursive Binary Search
- Steps Involved in the Recursive Approach
- Iterative Binary search
- Steps Involved in Iterative Approach
- Binary Search Complexity
- Time Complexity
- Space Complexity
- FAQs
- Conclusion
linear search and binary search in Python program
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 found at index ") else: print(f"Element not found in the array") 
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 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 found at index ") else: print(f"Element 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 found at index ") 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 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.
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.
Binary Search in Python
The process of finding an element from a collection of elements is known as searching. We have several techniques or ways of searching an element among several given elements, and these techniques are known as searching algorithms. Binary Search is one of the easiest search algorithms. Let us learn about the binary search in Python.
Binary Search in Python is a searching technique that works on a sorted array or list of elements. Instead of comparing every element of the list with the required element, the binary search algorithm repeatedly divides the list of elements into smaller segments. It then searches for the required element in the divided segments.
Recursive Binary Search
The recursive implementation of the binary search algorithm involves defining a recursive function that performs the search. It takes the sorted array, the target value to search for, and the range of indices to consider in the current recursive call.
Let us first know the recursive way. Suppose we want to search element E in the array.
We can call a function on the array with the required element E: BinarySearch(array, E). This function will return the index the element E.
Steps Involved in the Recursive Approach
- Compare E with the mid element.
- If E = = a r r a y [ m i d ] E == array[mid] E = = a r r a y [ m i d ] , then we return the mid index.
- Else if E > a r r a y [ m i d ] E > array[mid] E > a r r a y [ m i d ] , call the function BinarySearch function on the left half of the array.
- Else we call the function BinarySearch on the right half of the array.
We have to perform the above steps by keeping in mind the base condition that the low index should always be less than or equal to the high index.
Iterative Binary search
Iterative Binary Search is a search algorithm used to find a specific target value within a sorted array. It follows the principle of the Binary Search algorithm but utilizes an iterative approach instead of recursion.
Let us now discuss the iterative approach to implement binary search. Suppose, we want to search the same element E in the array.
We can call a function on the array with the required element E : BinarySearch(array, E). This function will return the index of element E.
Steps Involved in Iterative Approach
- Compare E with the mid element.
- If E = = a r r a y [ m i d ] E == array[mid] E = = a r r a y [ m i d ] , then we return the mid index.
- Else if E > a r r a y [ m i d ] E > array[mid] E > a r r a y [ m i d ] , then we shift the low index to mid + 1.
- Else, we shift the high index to mid - 1.
Binary Search Complexity
The time complexity of binary search in Python is better than linear search because we do not need to search over the entire array. We smartly divide the array into smaller sub-arrays and get our answer. So, binary search is a faster and more efficient algorithm, but it only works on the sorted array.
Time Complexity
When the desired element is directly found at the middle index, we get the best time complexity i.e., O ( 1 ) O(1) O ( 1 ) . On the other hand, if we cannot find the required element in the entire array, then we get the worst time complexity, i.e., O ( l o g n ) O(log n) O ( l o g n ) . The space is constant.
The average time complexity of the binary search in Python is O ( l o g n ) O (log n) O ( l o g n ) .
Space Complexity
We do not need any extra variable or data structure to find the result. So, the space complexity of the binary search is O ( 1 ) O(1) O ( 1 ) .
FAQs
Q. What is the difference between Binary Search and Linear Search?
A. Binary Search and Linear Search are two different algorithms used for searching elements in an array. Binary Search is an efficient algorithm that requires the array to be sorted and continually divides the search space in half, resulting in a time complexity of O(log n). On the other hand, Linear Search sequentially checks each element in the array until the target value is found or the end of the array is reached, resulting in a time complexity of O(n). Binary Search is significantly faster for large sorted arrays compared to Linear Search.
Q. Can Binary Search be applied to non-numeric data or custom objects?
A. Yes, Binary Search can be applied to non-numeric data or custom objects in Python. However, for Binary Search to work correctly, the data or objects must have a defined ordering. This ordering can be established by implementing comparison functions or operators that define the criteria for sorting and comparison.
Q. What happens if the array is not sorted in Binary Search?
A. If the array is not sorted, Binary Search cannot be directly applied. Binary Search relies on the array being sorted to divide the search space efficiently. In such cases, it is necessary to sort the array using a sorting algorithm (such as Python's built-in sort function or custom implementation) before performing Binary Search.
Q. Are there any limitations or prerequisites for using Binary Search?
A. Binary Search has a few prerequisites and limitations. Firstly, the array must be sorted in ascending or descending order. Additionally, the Binary Search algorithm assumes that the array elements are comparable using equality and relational operators. If the array contains duplicate values, Binary Search may not always return the first occurrence of the target value. To address this, additional logic can be added to handle such scenarios if necessary.
Conclusion
- Binary Search in python is a searching technique that works on a sorted array or list of elements.
- The binary search algorithm repeatedly divides the list of elements into smaller segments and then searches the required element in the divided segments.
- Binary Search follows the principle of the divide and conquer technique.
- Binary Search is better than linear search.
- Binary Search is one of the fastest searching algorithms.
- We can implement binary search both iteratively and recursively.
- The average time complexity of the binary search in Python is O ( l o g n ) O (log n) O ( l o g n ) , and the space complexity of the binary search in Python is O ( 1 ) O(1) O ( 1 ) .