Binary Search in Python
Introduction to Binary Search in Python
Binary Search in Python enhance your search strategies using the binary search algorithm in Python. Acquire a step-by-step grasp of binary search implementation, comprehend its principles and real-world applications, and delve into practical instances. Leverage the advantages of logarithmic time complexity for swift data retrieval. Begin your journey towards becoming a proficient binary search practitioner today!
What is Searching Technique?
Searching refers to the process of locating a specific element, value, or data within a collection, such as an array, list, or database.
In Python, searching can be categorized into two main types:
- Linear Search
- Binary Search
Binary Search in Python
Binary search is a fast and efficient algorithm for finding a target value within a sorted collection by repeatedly dividing the search space in half and quickly converging to the desired element.
Binary Search uses two methods to find the target element :
- Recursive Method
- Iterative Method
Binary Search Algorithm
1. Set two pointers low and high for the given array.
2. From the given array; find the middle element i.e. mid = (low+high)/2.
3. If x==mid, then simply return mid, else compare the element with the middle element.
4. If x>mid, then set low = mid+1 and find the middle element.
5. If x<mid, then set high = mid-1 and find the middle element.
6. Repeat steps 2 to 6 until we find the target element i.e. ‘x’.
7. If low=high, we found that element x=5.
Binary Search in Python Methods:
1. Recursive Method
The recursive method for binary search in Python involves breaking down the search process into smaller subproblems by dividing the sorted array into halves. At each step, the middle element is compared to the target value. If they are equal, the search is successful. If the middle element is greater than the target, the search recurs on the left half; if it’s smaller, the search recurs on the right half.
binarySearch(arr, x, low, high)
if low > high
return False
else
mid = (low + high) / 2
if x == arr[mid]
return mid
else if x > arr[mid] //when x is on the right side
return binarySearch(arr, x, mid + 1, high)
else //when x is on the left side
return binarySearch(arr, x, low, mid - 1)
2. Iterative Method
In this method, the entire sorted array serves as the search range. In each iteration, the middle element of the current interval is compared to the target value. If they match, the search is successful. If the middle element is greater than the target, the interval is adjusted to the left half; if it’s smaller, the interval shifts to the right half. This process iterates until the interval becomes empty or the target is found.
do until the pointers low and high meet each other.
mid = (low + high)/2
if (x == arr[mid])
return mid
else if (x > arr[mid]) //when x is on the right side
low = mid + 1
else // when x is on the left side
high = mid - 1
Python Examples(Iterative Method)
def binary_search_iterative(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
sorted_list = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target_element = 11
result = binary_search_iterative(sorted_list, target_element)
if result != -1:
print(f"Element {target_element} found at index {result} using iterative binary search")
else:
print("Element not found")
Python Examples(Recursive Method)
def binary_search_recursive(arr, target, left, right):
if left > right:
return -1
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, right)
else:
return binary_search_recursive(arr, target, left, mid - 1)
def binary_search_recursive_wrapper(arr, target):
return binary_search_recursive(arr, target, 0, len(arr) - 1)
sorted_list = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target_element = 11
result = binary_search_recursive_wrapper(sorted_list, target_element)
if result != -1:
print(f"Element {target_element} found at index {result} using recursive binary search")
else:
print("Element not found")
Binary Search in Python using list
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 usage:
my_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 5
result = binary_search(my_list, target)
print("Element", target "found at index", result.)
Output :
Element 5 found at index 4
Explanation :
Binary search efficiently finds a target value within a sorted list. It compares the target to the middle element and narrows the search range based on whether the target is greater or smaller. This process repeats until the target is found or the search range becomes empty. In the example, the target 5 is found at index 4, demonstrating the algorithm’s efficiency.
Binary Search in Python using for loop
my_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 5
left, right = 0, len(my_list) - 1
for _ in range(len(my_list)):
mid = (left + right) // 2
if my_list[mid] == target:
print("Target", target, "found at index", mid)
break
elif my_list[mid] < target:
left = mid + 1
else:
right = mid - 1
else:
print("Target", target, "not found.")
Output :
Element 5 found at index 4
Explanation :
This Python binary search implementation uses a ‘for‘ loop. It efficiently locates a target value in a sorted list, adjusting the search range based on comparisons with the middle element. In the example, it successfully finds the target 5 at index 4, demonstrating the algorithm’s effectiveness.
Binary Search in Python without using function
my_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 5
left, right = 0, len(my_list) - 1
while left <= right:
mid = (left + right) // 2
if my_list[mid] == target:
print("Target", target, "found at index", mid)
break
elif my_list[mid] < target:
left = mid + 1
else:
right = mid - 1
else:
print("Target", target, "not found.")
Output :
Element 5 found at index 4
Explanation :
This Python binary search implementation doesn’t use a separate function. It efficiently finds a target value in a sorted list by iteratively narrowing the search range based on comparisons with the middle element. In the example, it successfully finds the target 5 at index 4, and if not found, it prints that the target is not found.
Binary Search using User Input
# Get user input for the target and list
target = int(input("Enter the target number: "))
my_list = sorted(map(int, input("Enter a sorted list of numbers separated by spaces: ").split()))
left, right = 0, len(my_list) - 1
while left <= right:
mid = (left + right) // 2
if my_list[mid] == target:
print("Target", target, "found at index", mid)
break
elif my_list[mid] < target:
left = mid + 1
else:
right = mid - 1
else:
print("Target", target, "not found.")
Output :
Enter the target number: 5 Enter a sorted list of numbers separated by spaces: 1 2 3 4 5 6 7 8 9
Result : Target 5 found at index 4
Explanation :
This Python binary search program takes user input for a target number and a sorted list of numbers. It then efficiently finds the target value within the list by iteratively adjusting the search range based on comparisons with the middle element. The program prints the target’s index if found or a message indicating it was not found.
Time Complexity for Binary Search
The time complexity of the binary search algorithm in Python is O(1) for the best case and O(logn) for the worst and average case, where “n” represents the number of elements in the list or array being searched.
There are mainly three case for Time complexity :
- Best Case : O(1)
- Average Case : O(logn)
- Worst Case : O(logn)
Conclusion
Throughout this guide, we’ve delved into the intricacies of binary search, from its fundamental principles to its step-by-step implementation in Python. Remember that while binary search offers exceptional speed advantages, it’s essential to work with sorted data to fully leverage its benefits.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Question 1.
What are the advantages of binary search?
Binary search has a logarithmic time complexity of O(log n), making it highly efficient for large datasets. It outperforms linear search (O(n)) for sorted arrays.
Question 2.
What happens if the array is not sorted for binary search?
Binary search requires a sorted dataset. If the array is not sorted, the algorithm will not produce accurate results.
Question 3.
Can binary search be applied to linked lists?
Yes, binary search can be applied to linked lists, but it’s less straightforward than with arrays due to the lack of direct indexing. It requires converting linked list elements into an array-like structure.
Question 4.
Are there any limitations to binary search?
Binary search is limited to sorted datasets. It might not be the best choice for small datasets or datasets that frequently change, as sorting incurs an additional cost.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment