Skip to main content

Python Binary Search

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:

python binary search 1

Step 2:

python binary search 2

Step 3:

python binary search 3

Step:4

python binary search 4

Algorithm:

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):

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):

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.

The post Python Binary Search appeared first on The Crazy Programmer.



from The Crazy Programmer https://www.thecrazyprogrammer.com/2017/11/python-binary-search.html
Labels:

Comments

Post a Comment

Popular posts from this blog

dotnet sdk list and dotnet sdk latest

Can someone make .NET Core better with a simple global command? Fanie Reynders did and he did it in a simple and elegant way. I'm envious, in fact, because I spec'ed this exact thing out in a meeting a few months ago but I could have just done it like he did and I would have used fewer keystrokes! Last year when .NET Core was just getting started, there was a "DNVM" helper command that you could use to simplify dealing with multiple versions of the .NET SDK on one machine. Later, rather than 'switching global SDK versions,' switching was simplified to be handled on a folder by folder basis. That meant that if you had a project in a folder with no global.json that pinned the SDK version, your project would use the latest installed version. If you liked, you could create a global.json file and pin your project's folder to a specific version. Great, but I would constantly have to google to remember the format for the global.json file, and I'd constan...
Post a Comment
Read more

15 Web Design Trends to Watch in 2018

The modern world is full of extraordinary things that influence our imagination and mood. Our soul needs a perfect atmosphere and impressive spots. To apply such things in practice, we have submitted the list of the web trends that deserve your attention. Robert frost design analysis will meet all your wishes and expectations. Image Source Web Design Trends to Watch in 2018 1. More Organic Shapes Until this year, web design, as well as mobile design, were based on the right-angled and sharp-edged shapes. However, it seems that this year will bring some significant changes in the field of web design. The recent trends will offer the absolute rounded corners. In addition, the web design of 2018 will make the real things look like the cartoonish ones. 2.   Bold Minimalism Although some of you may think that this web design trend will not attract the Internet users. Indeed, the notion of minimalism is often associated with boredom and dullness. However, in this case, bold ...
Post a Comment
Read more

R vs Python for Machine Learning

There are so many things to learn before to choose which language is good for Machine Learning. We will discuss each and everything about R as well as Python and the situation or problem in which situation we have to use which language. Let’s start Python and R are the two most Commonly used Programming Languages for Machine Learning and because of the popularity of both the languages Novice or you can say fresher are getting confused, whether they should choose R or Python language to commence their career in the Machine learning domain. Don’t worry guys through this article we will discuss R vs Python for Machine Learning. So, without exaggerating this article let’s get started. We will start it from the very Basics things or definitions. R vs Python for Machine Learning Introduction R is a programming language made by statisticians and data miners for statistical analysis and graphics supported by R foundation for statistical computing. R also provides high-quality graphics and...
1 comment
Read more