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

Rail Fence Cipher Program in C and C++[Encryption & Decryption]

Here you will get rail fence cipher program in C and C++ for encryption and decryption. It is a kind of transposition cipher which is also known as zigzag cipher. Below is an example. Here Key = 3. For encryption we write the message diagonally in zigzag form in a matrix having total rows = key and total columns = message length. Then read the matrix row wise horizontally to get encrypted message. Rail Fence Cipher Program in C #include<stdio.h> #include<string.h> void encryptMsg(char msg[], int key){ int msgLen = strlen(msg), i, j, k = -1, row = 0, col = 0; char railMatrix[key][msgLen]; for(i = 0; i < key; ++i) for(j = 0; j < msgLen; ++j) railMatrix[i][j] = '\n'; for(i = 0; i < msgLen; ++i){ railMatrix[row][col++] = msg[i]; if(row == 0 || row == key-1) k= k * (-1); row = row + k; } printf("\nEncrypted Message: "); for(i = 0; i < key; ++i) f...
3 comments
Read more

Data Encryption Standard (DES) Algorithm

Data Encryption Standard is a symmetric-key algorithm for the encrypting the data. It comes under block cipher algorithm which follows Feistel structure. Here is the block diagram of Data Encryption Standard. Fig1: DES Algorithm Block Diagram [Image Source: Cryptography and Network Security Principles and Practices 4 th Ed by William Stallings] Explanation for above diagram: Each character of plain text converted into binary format. Every time we take 64 bits from that and give as input to DES algorithm, then it processed through 16 rounds and then converted to cipher text. Initial Permutation: 64 bit plain text goes under initial permutation and then given to round 1. Since initial permutation step receiving 64 bits, it contains an 1×64 matrix which contains numbers from 1 to 64 but in shuffled order. After that, we arrange our original 64 bit text in the order mentioned in that matrix. [You can see the matrix in below code] After initial permutation, 64 bit text passed throug...
Post a Comment
Read more

Accessibility Insights for the Web and Windows makes accessibility even easier

I recently stumbled upon https://accessibilityinsights.io . There's both a Chrome/ Edge extension and a Windows app, both designed to make it easier to find and fix accessibility issues in your websites and apps. The GitHub for the Accessibility Insights extension for the web is at https://github.com/Microsoft/accessibility-insights-web and they have three trains you can get on: Canary (released continuously) Insider (on feature completion) Production (after validation in Insider) It builds on top of the Deque Axe core engine with a really fresh UI. The "FastPass" found these issues with my podcast site in seconds - which kind of makes me feel bad, but at least I know what's wrong! However, the most impressive visualization in my opinion was the Tab Stop test! See below how it draws clear numbered line segments as you Tab from element. This is a brilliant way to understand exactly how someone without a mouse would move through your site. I can easily s...
1 comment
Read more