- Prepare
All Platforms Programming Aptitude Syllabus Interview Preparation Interview Exp. Off Campus - Prime Video
- Prime Mock

- Prime Video
- OffCampus Updates
- Placement Stats
- Prime Video
- Prime Mock

^{0}Notifications Mark All Read

- Login
- Get Prime

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

**is also known as "Divide and Conquer Method". This approach involves a function invoking itself repeatedly until it locates an element within the list.**

*Recursive Method***
How Binary Search in Python Works ?
**

**‘x = 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.

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

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