Program for Binary Search in Python

Introduction

To search the element x through binary search, we need a sorted array list.

Program for Binary Search in Python

Program

Approach 1: Iterative

def search(ip_arr, x):

    l = 0

    h = len(ip_arr) - 1

    mid = 0

    while l <= h:

        mid = (h + l) // 2

        if ip_arr[mid] < x:

            l = mid + 1

        elif ip_arr[mid] > x:

            h = mid - 1

        else:

            return mid

    return -1

   

ip_arr = [101, 4, 98, 7]

x = 98

output = search(ip_arr, x)

if output != -1:

    print("The element is present at index", str(output))

else:

    print("The element is not present in the given array!")

Output

Program for Binary Search in Python Output

Approach 2: Recursive

Program for Binary Search in Python 2

Output:

Program for Binary Search in Python Output 2

Explanation

In the above python program, below steps are followed for Binary Search:

  1. Divide the sorted list into two equal half’s and compare the middle element with the x (search element).
  2. If x equalled to middle element of list, the value is returned.
  3. Else if x is greater than the middle element, the right half is treated as the list and again step 1 to step 4 is followed.
  4. Else if x is less than the middle element, the left half is treated as the list and steps 1 to 4 is followed.
  5. If the searched element is found, the value True is returned else False is returned.

Author

  • Barry Allen

    A Full Stack Developer with 10+ years of experience in different domain including SAP, Blockchain, AI and Web Development.


Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.