Here you will learn about python binary search with program and algorithm.
In linear search, we have to check each node/element. Because of this, time complexity increases. To reduce this time complexity, we use Binary search. In Binary search half of the given array will be ignored after just one comparison.
The main point to be noted is Binary Search only works for sorted array.
If the array is sorted into ascending order, all we have to do is find the middle index of the array and then compare the element at middle index with the element to find. If our given element is greater than the element at middle index then we’ll ignore the left half array and the array will start from the next index of middle index.
On other hand, if the given element is less than the element presents at middle index, then we’ll ignore the right half array and the new array will ends with left one index of middle index.
If the given element is equal to the element presents on the middle index, then search is completed.
In the case, the first index is greater than the last index of array, it means we have been gone through the entire array and the given element is not presented in the array.
Python Binary Search
Example:
We’ve a sorted array [2, 14, 19, 21, 99, 210, 512, 1028, 4443, 5110] and the element to be find is 4443.
Step 1:
Step 2:
Step 3:
Step:4
Algorithm:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
Binary_search [arr, starting index, last index, element] Step:1- mid = (starting index + last index) / 2 Step:2- If starting index > last index Then, Print "Element not found" Exit Else if element > arr[mid] Then, starting index = mid + 1 Go to Step:1 Else if element < arr[mid] Then, last index = mid - 1 Go to Step:2 Else: { means element == arr[mid] } Print "Element Presented at position" + mid Exit |
Program for Binary Search in Python
Iterative Approach (Using Loop):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
def Binary_search(arr,start_index,last_index,element): while (start_index<= last_index): mid =(int)(start_index+last_index)/2 if (element>arr[mid]): start_index = mid+1 elif (element<arr[mid]): last_index = mid-1 elif (element == arr[mid]): return mid return -1 arr = [2,14,19,21,99,210,512,1028,4443,5110] element = 4443 start_index = 0 last_index = len(arr)-1 found = Binary_search(arr,start_index,last_index,element) if (found == -1): print "element not present in array" else: print "element is present at index " + str(found) |
Output
element is present at index 8
Recursive Approach (Using Recursion):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
def Binary_search(arr,start_index,last_index,element): mid =(int)(start_index+last_index)/2 if(start_index>last_index): print "Element not found" elif (element>arr[mid]): start_index = mid+1 Binary_search(arr,start_index,last_index,element) elif (element<arr[mid]): last_index = mid-1 Binary_search(arr,start_index,last_index,element) else: print "element is present at index " + str(mid) arr = [2,14,19,21,99,210,512,1028,4443,5110] element = 99 start_index = 0 last_index = len(arr)-1 Binary_search(arr,start_index,last_index,element) |
Output
element is present at index 4
Comment below if you have any queries related to above python binary search algorithm tutorial.
so easy. and understanding for everyone
Great post and nice explanation.
One question though…
Why use this syntax for type conversion?
mid = (int)(start_index+last_index)/2
It is used in C language and i’m not sure these are same things.
This works for any function
>>> def f(a):
… return a + 1
…
>>> (f)(1.5)
2.5
>>>
You’ve could have done this
mid = int((start_index+last_index)/2)
which makes more sense in python, also it seems you are using python2 in which ‘/’ operator returns integer if the operands are integers, so type conversion is unnecessary.
how to develop our coding skills
loop approach is wrong
your program is not working please check it
Hello,
The program does not give the correct output in case of data(input value) duplication.
Please rectify the bug in the program.
Regards,
Utkarsh