Python-All-Programming-Codes/mod1.py at main · ShubhamMahajan880/Python-All-Programming-Codes · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
"""

Docstring:- This Module Contains Binarty Search Implementation
Docstring command is description of that particular module


"""


#Recursuve Function in python:-
""" If a function call it self again and again is known as recursive function

factorial(5) = 5 * fact(4)
                       4 * fact(3)
                           3 * fact(2)
                                   2 * fact(1)
                                           1   """ # Such a problems can be easily solve by recursion
def factorial(num):
    if num == 1:
        return 1
    else:
        return num * factorial(num-1)

num1 = 5
result = factorial(num1)
print(result) # 120

""" About Binary search:-
l = [100,200,300,400,500,600,700,800,900]
key = 700

mid  = 9/2 = 4 = 500 == 700 True ( Here in division ignore the decimal part )

( Since it's an sorted array that's why we can say that if element is Greater than mid then it will be present at Right Hand Side of mid similarly if the element is lesser than mid then it will be present at Left Hand Sidde of mid

[600,700,800,900]

mid = 4/2 = 2
800 == 700

[600,700]
mid = 2/2 = 1

700 == 700 return True
"""

def binary_search(l,key):
    """
    Binary Search:- Input a list and key return true if key exist else return false


    """
    mid = len(l)//2 # Here we want mid as integer format only that's why we used Floor division operator here

    if l[mid] == key:
        return True

    elif key < l[mid]:
        return binary_search(l[:mid],key)#Since key element is less than mid tha's why it will be present at L.H.S. of mid So use slicing anf initialize from zero to  mid
    else:
        return binary_search(l[mid+1:],key)# initialize from mid+1 to end of the list

#print(__name__)# __main__ ( So python is by dedault named it as __main__
if __name__ == '__main__':


    l = [100,200,300,400,500,600,700,800,900]
    key = 700
    result = binary_search(l,key)
    print(result)#True ( So it's working )

l = [100,200,300,400,500,600,700,800,900]
key = 100

result = binary_search(l,key)
print(result)#True ( So it's working )

"""
l = [100,200,300,400,500,600,700,800,900]
key = 1000

result = binary_search(l,key)
print(result) #IndexError: list index out of range
"""


def binary_search(l,key):

    if len(l) == 0:
        return False
    else:

        mid = len(l)//2 # Here we want mid as integer format only that's why we used Floor division operator here
        if l[mid] == key:
            return True

        elif key < l[mid]:
            return binary_search(l[:mid],key)#Since key element is less than mid tha's why it will be present at L.H.S. of mid So use slicing anf initialize from zero to  mid
        else:
            return binary_search(l[mid+1:],key)# initialize from mid+1 to end of the list

l = [100,200,300,400,500,600,700,800,900]
key = 100
result  = binary_search(l,key)
print(result) # True