By using this site, you agree to the Privacy Policy and Terms of Use.
Accept
rocoderesrocoderes
  • Home
  • HTML & CSS
    • Login and Registration Form
    • Card Design
    • Loader
  • JavaScript
  • Python
  • Internet
  • Landing Pages
  • Tools
    • Google Drive Direct Download Link Generator
    • Word Count
  • Games
    • House Painter
Notification Show More
Latest News
Responding to and Tracking Key Presses
How to Work With Responding to and Tracking Key Presses
JavaScript
Passing a JavaScript Value Between HTML Pages
Passing a JavaScript Value Between HTML Pages
JavaScript
Compare Objects in an Array
JavaScript Problem: Compare Objects in an Array
JavaScript
Switching Name Order Using Capturing Groups in Regular Expressions
Switching Name Order Using Capturing Groups in Regular Expressions
JavaScript
Shuffling an Array
JavaScript Problem: How to Perform Shuffling an Array
JavaScript
Aa
Aa
rocoderesrocoderes
Search
  • Home
  • HTML & CSS
    • Login and Registration Form
    • Card Design
    • Loader
  • JavaScript
  • Python
  • Internet
  • Landing Pages
  • Tools
    • Google Drive Direct Download Link Generator
    • Word Count
  • Games
    • House Painter
Follow US
High Quality Design Resources for Free.
rocoderes > Python > What is Binary Search Algorithm in python?
Python

What is Binary Search Algorithm in python?

Admin
Last updated: 2022/11/23 at 5:19 AM
Admin
Share
6 Min Read
binary search algorithm in python

Today, we will learn about binary search algorithm in python. Binary search applies to the sorted array or to a larger size list. The complexity of O (log n) time makes it much faster compared to other sorting algorithms. The only limitation is that the list or item list must be sorted in order to use the binary search algorithm.

Contents
How Binary Search Works?Features of binary Search algorithmImplementing Binary Search Algorithm 

Binary search looks for a particular item by comparing the middlemost item of the collection. If a match occurs, then the index of the item is return. If the middle item is greater than the item, then the item is search in the sub-array to the left of the middle item. Otherwise, the item is searched for in the sub-array to the right of the middle item. This process continues on the sub-array as well until the size of the subarray reduces to zero.

How Binary Search Works?

For a binary search to work, the target list must be sorted. We will learn the binary search process with a symbolic example. The following is our sorted array and let’s imagine we need to search the location of value 99 using a binary search algorithm.

Binary Search Algorithm in python 1

First, we shall determine half of the array by using this formula −

mid =( beg + last ) / 2

Here it is, (0 + 9 ) / 2 = 4 (integer value of 4.5). So, 4 is the mid of the array.

Binary Search Algorithm in python2

Now we compare the value stored at location 4, with the value being searched, i.e. 99. We find that the value at location 4 is 55, which is not a match. As the value is greater than 55 and we have a sorted array, so we also know that the target value must be in the upper portion of the array.

We change our beg to mid + 1 and find the new mid value again.

beg= mid + 1

mid =( beg + last ) / 2

mid=(5 + 9) / 2 =7

Our new mid is 7 now. We compare the value stored at location 7 with our target value 99.

Binary Search Algorithm in python 3

The value stored at location 7 is not a match, rather it is more than what we are looking for. so we also know that the target value must be in the upper portion of the array.

We change our beg to mid + 1 and find the new mid value again.

beg= mid + 1

mid =( beg + last ) / 2

mid=(8 + 9) / 2=8

Our new mid is 8 now. We compare the value stored at location 8 with our target value 99.

Binary Search Algorithm in python 4

We find that it is a match.We conclude that the target value 99 is stored at location 8.

Now second Example let’s imagine we need to search the location of value 22.

beg=0 and last=9

mid=(0 + 9) / 2 = 4

Here mid is 4 now. We compare the value stored at location 4 with our target value 22. its not match

so last= mid – 1

beg=0 and last =4 – 1

mid=(0 + 3 ) / = 1

Here mid is 1 now. We compare the value stored at location 1 with our target value 22. its match

Features of binary Search algorithm

1.Binary search is a fast search algorithm. This search algorithm works on the principle of divide and conquer.

2.It is faster than sequential search

3.It reduces the span of searching the value

4.Best Case :CBest(n)=1

5.Worst Case :CWorst(n)=O(logn)

6.Average Case :CAvg(n)=O(logn)

Implementing Binary Search Algorithm 

Following are the steps of implementation that we will be following:

  1. Start with the middle element:
    • Here If the target value is equal to the middle element of the array, then return the index of the middle element.
    • If not, then compare the middle element with the target value,
      • If the target value is greater than the number in the middle index, then pick the elements to the right of the middle index, and start with Step 1.
      • else if the target value is less than the number in the middle index, then pick the elements to the left of the middle index, and start with Step 1.
  2. When a match is found, return the index of the element matched.
  3. If no match is found, then return Element is not Found

def binarySearch(arr,item):
    beg=0
    last=len(arr)-1
    while beg<=last:
        mid = (beg + last) // 2
        if item==arr[mid]:
            return mid
        if item>arr[mid]:
            beg=mid+1
        else:
            last=mid-1
    else:
        return False
arr=[]
arr_size=int(input("Enter The Size Of the Array: "))
for i in range(arr_size):
    arr_element=int(input("Enter The The Element in Acceding order At "+str(i)+" : "))
    arr.append(arr_element)

item=int(input("Enter Element You Want To Search: "))
result=binarySearch(arr,item)
if result:
    print(f"Element Found In {result}")
else:
    print("Element is not Found")

Full source code:

Related

Subscribe to Our Newsletter

Subscribe to our newsletter to get our newest articles instantly!

TAGGED: binary search algorithm in python
Share this Article
Facebook Twitter Email Print
What do you think?
Love0
Sad0
Happy0
Sleepy0
Angry0
Dead0
Wink0
Posted by Admin
Follow:
Rocoderes is a blog you can learn HTML, CSS, JavaScript, React Js and Python along with creative coding stuff and free source code files.
Previous Article To-Do List using JavaScript How to Make To-Do List using JavaScript
Next Article speed typing game using javascript How to Make Speed Typing Game using JavaScript
Leave a comment Leave a comment

Leave a Reply Cancel reply

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

- Advertisement -

You Might Also Like

Rock Paper Scissors Python

How To Make Rock Paper Scissors Python Game 2022

November 26, 2022
python QR code generator

How To Make Python QR Code Generator

November 25, 2022
Countdown Calendar using Python Tkinter

How to Make Countdown Calendar using Python Tkinter

November 24, 2022

What is Linear search in python?

November 23, 2022
rocoderesrocoderes
Follow US

Copyright © 2022 All Right Reserved By Rocoderes

  • Home
  • About us
  • Contact us
  • Disclaimer
Join Us!

Subscribe to our newsletter and never miss our latest news, podcasts etc.

Zero spam, Unsubscribe at any time.
Welcome Back!

Sign in to your account

Lost your password?