w3resource

Python: Binary search


1. Binary Search

Write a Python program for binary search.
Binary Search : In computer science, a binary search or half-interval search algorithm finds the position of a target value within a sorted array. The binary search algorithm can be classified as a dichotomies divide-and-conquer search algorithm and executes in logarithmic time.

Step by step example :

Binary search Part - 1


Binary search Part - 2


Binary search Part - 3

Binary search Part - 4

Sample Solution:

Python Code:

def binary_search(item_list,item):
	first = 0
	last = len(item_list)-1
	found = False
	while( first<=last and not found):
		mid = (first + last)//2
		if item_list[mid] == item :
			found = True
		else:
			if item < item_list[mid]:
				last = mid - 1
			else:
				first = mid + 1	
	return found
	
print(binary_search([1,2,3,5,8], 6))
print(binary_search([1,2,3,5,8], 5))

Sample Output:

False                                                                                                         
True

Flowchart:

Flowchart: Python Data Structures and Algorithms: Binary search

For more Practice: Solve these Related Problems:

  • Write a Python program to implement a binary search that returns the index of the target element if found, otherwise returns -1.
  • Write a Python program to perform binary search on a sorted list of strings and output the position of a given string.
  • Write a Python function to implement recursive binary search and count the number of comparisons made during the search.
  • Write a Python program that uses binary search to determine if a target value exists in a sorted list of floating-point numbers with a tolerance for rounding errors.

Go to:


Previous: Python Search and Sorting Exercise Homes.
Next: Write a Python program for sequential search.

Python Code Editor :

Contribute your code and comments through Disqus.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Follow us on Facebook and Twitter for latest update.