# 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.

#### How Binary Search in Python Works ?

The following steps are followed for finding elementx = 5′  from the given array : ### 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. ### 5. If x<mid, then set high = mid-1 and find the middle element. ### 7. If low=high, we found that element x=5. #### 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:
```

#### 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:

```

### 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.

### 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