ADVERTISEMENT
ADVERTISEMENT

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

ADVERTISEMENT
ADVERTISEMENT

Preparation

What's New

ADVERTISEMENT

Top Interview Coding Problems/Challenges!

ADVERTISEMENT

ADVERTISEMENT

Comments and Discussions!

ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.