Python Tutorial

# Binary Search Python Program

## What is binary search ?

• Binary search is used only on a sorted collection of elements.
• Most commonly used techniques that is used to solve problems.
• Number of iterations can be reduced in binary search on the basis of the value that is being searched.
Example, consider sorted collection of elements Binary search: reduces the number of iterations to search the particular element (only 3 iterations in below example). ## Binary Search Time complexity

Binary search performs the search operation on the other half in every steps. This results in a worst case time complexity of O(log2N), where N is the number of elements in the collection.

## Binary Search Python Program

```#!/usr/bin/python

def binary_search(search_key, list_vals):
low_index = 0;
high_index = len(list_vals);
while(low_index <= high_index):
mid_index = (low_index + high_index)/2;
if (list_vals[mid_index] < search_key):
low_index = mid_index + 1;
elif (list_vals[mid_index] > search_key):
high_index = mid_index - 1;
else:
return mid_index;
return -1;

if __name__ == "__main__":
list_vals = [10, 20, 30, 40, 50, 60, 70, 80];
key = int(raw_input("Please enter a string:"));
print("key is found at index: %d" % binary_search(key, list_vals));
```
Output:
```\$ python binary-search.py
key is found at index: 2
\$ python binary-search.py
key is found at index: 3
\$ python binary-search.py
key is found at index: -1
```

## Linear Search Python Program using recursive function

```#!/usr/bin/python

def binary_search(low_index, high_index, search_key, list_vals):
if(low_index <= high_index):
mid_index = (low_index + high_index)/2;
if (list_vals[mid_index] < search_key):
low_index = mid_index + 1;
elif (list_vals[mid_index] > search_key):
high_index = mid_index - 1;
else:
return mid_index;
return binary_search(low_index, high_index, search_key, list_vals);
return -1;

if __name__ == "__main__":
list_vals = [10, 20, 30, 40, 50, 60, 70, 80];
key = int(raw_input("Please enter a string:"));
low_index = 0;
high_index = len(list_vals);
print("key is found at index: %d" % binary_search(low_index, high_index, key, list_vals));

```
Output:
```\$ python binary-search.py
key is found at index: 2
\$ python binary-search.py
key is found at index: 3
\$ python binary-search.py
key is found at index: -1
```

Python Tutorial

## Python installation

Privacy Policy  |  Copyright 2020 - All Rights Reserved.  |  Contact us   |  Report website issues in Github   |  Facebook page   |  Google+ page     ^