Binary search

 In this post lets see how the binary search work and its algorithm with example.

Binary search works on divide and conquer method which means it divide the process into small unit and calculate it. Atlast again combine and shows the output.

This also use recursion function. It is nothing but calling a function again and again is call recursion function.

Lets see the Algorithm with example:

Before that binary search works only in sorted elements

L = [2, 4, 7, 10, 30, 47, 78, 82, 90, 92, 100]

1) lets consider search element as 7

2) Now the list is divided into two halfs by using mid value

  mid = start+end/2

  That is mid=0+10/2 = 10/2 =5

  Value present in position 5 is 47 so now mid value is 47

3) Next we follow three condition

  (i)   7 = mid value

  (ii)  7 > mid value

  (iii) 7 < mid value

Here condition (iii) satisfies because 7 is less than mid value(47). That is 7  present in the left side of the mid value. So complier doesn't check the right side values. It will just ignore it

You can ask why the number should be in left side, why can't it be in right side?. Defenity not because it is a sorted list so 7 must be present in the left side that is before mid value(47).

4) Next step again follows step 3 that is. Now the left side of elements are

[2, 4, 7, 10, 30]

Again it finds the mid value 

Mid val= 0+5/2 = 5/2 = 2(float value)

Again check the condition 

Now 7= mid value

So the number is present in index 2

To find elements in right side:

 lets consider search element as: 92

1) find mid value (already found)

mid value = 47

2) 92> 47 condition (ii) satisfies

Now it search 92 in right side because right side as numbers great than 47 so now elements are

[78, 82, 90, 92, 100]

Again lets find mid value. Here the starting value is 6 so

mid value = 6+10/2 = 16/2 = 8

The element present in position 8 is 90

3) Again step 2, now condition (iii) satisfies that is 92>mid value  so it search in right side. Now elements are

[92,100]

Again lets fine mid value. Here the starting value is 9 so

mid value = 9+10/2 = 19/2 = 9(float value)

The element present in position 9 is 92

4) condition (i) satisfies that is 92= mid value

So the number is present in position 9.

Code for binary search:

def binarySearch(arr, l, r, x):

 

    while l <= r:

 

        mid = l + (r - l) // 2

         

        # Check if x is present at mid

        if arr[mid] == x:

            return mid

 

        # If x is greater, ignore left half

        elif arr[mid] < x:

            l = mid + 1

 

        # If x is smaller, ignore right half

        else:

            r = mid - 1

     

    # If we reach here, then the element

    # was not present

    return -1

 

arr = [ 2, 3, 4, 10, 40 ]

x = int(input("Enter the number:"))

 

# Function call

result = binarySearch(arr,0,len(arr)-1, x)

 

if result != -1:

   print ("Element is present at index" , result)

else:

   print ("Element is not present in array")

Output:

Enter the number:3

Element is present at index 1

Hope you understand the program and try yourself for more clear view feel free to comment your thoughts!!    

Book for python:  https://amzn.to/3pCgIqy

ebook: https://amzn.to/3pHioiO