w3resource

Python Data Structures and Algorithms: Binary search

Python Search and Sorting : Exercise-1 with Solution

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

Visualize Python code execution:

The following tool visualize what the computer is doing step-by-step as it executes the said program:

Python Code Editor :

Contribute your code and comments through Disqus.

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

What is the difficulty level of this exercise?

Test your Python skills with w3resource's quiz



Python: Tips of the Day

Does Python have a ternary conditional operator?

The expression syntax is:

a if condition else b

First condition is evaluated, then exactly one of either a or b is evaluated and returned based on the Boolean value of condition. If condition evaluates to True, then a is evaluated and returned but b is ignored, or else when b is evaluated and returned but a is ignored.

This allows short-circuiting because when condition is true only a is evaluated and b is not evaluated at all, but when condition is false only b is evaluated and a is not evaluated at all.

Example:

>>> 'true' if True else 'false'
>>> 'true' if False else 'false'

Output:

'true'
'false'

Note that conditionals are an expression, not a statement. This means you can't use assignment statements or pass or other statements within a conditional expression:

Example:

>>> pass if False else x = 3

Output:

  File "<stdin>", line 1
    pass if False else x = 3
          ^
SyntaxError: invalid syntax

You can, however, use conditional expressions to assign a variable like so:

x = a if True else b

Think of the conditional expression as switching between two values. It is very useful when you're in a 'one value or another' situation, it but doesn't do much else.

If you need to use statements, you have to use a normal if statement instead of a conditional expression.

Ref: https://bit.ly/2zhDfU0