Home » Python » Python programs

# Python program for Binary Search

**Binary search in python**: Here, we are going to learn to **implement a binary search in an array or list in python**.

Submitted by Sanjeev, on April 04, 2019

**Binary Search**: Binary search is a searching algorithm which is used to search a number in a sorted array or list.

**Description:**

**Binary search** uses **Decrease and Conquer Algorithm**. In this algorithm original problem is decreased by a constant factor and a sub-problem is created and then the sub-problem is further solved to get the solution of the original problem. This process keeps on going unless the problem is solved or no further division is possible.

**Procedure for Binary Search:**

First sort the array (ascending or descending totally depends upon user) Start = 0, end = length (array) – 1 Mid = (start + end) / 2 While start is less than end If array[mid] == number Print number found and exit If array[mid] > number End = mid – 1 Mid = (start + end) / 2 If array[mid] < number Start = mid + 1 Mid = (start + end) / 2 End of while

**Time Complexity : O(logn)**

**Note:** For binary search array or list needs to be sorted before searching otherwise one may not get correct result.

### Python code for binary search

def binary_search(l, num_find): ''' This function is used to search any number. Whether the given number is present in the list or not. If the number is present in list the list it will return TRUE and FALSE otherwise. ''' start = 0 end = len(l) - 1 mid = (start + end) // 2 # We took found as False that is, initially # we are considering that the given number # is not present in the list unless proven found = False position = -1 while start <= end: if l[mid] == num_find: found = True position = mid break if num_find > l[mid]: start = mid + 1 mid = (start + end) // 2 else: end = mid - 1 mid = (start + end) // 2 return (found, position) # Time Complexity : O(logn) # main code if __name__=='__main__': l = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] num = 6 found = binary_search(l, num) if found[0]: print('Number %d found at position %d'%(num, found[1]+1)) else: print('Number %d not found'%num)

**Output**

Number 6 found at position 7

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions