This is my 43th day of #100DaysofCode and #python. Today Some time learned more about numpy. And studied more about algorithm. In algorithm I studied about liner search and binary search.

While studied I learned that linear search is a method for finding an element within a list, which sequentially check each element in the list until the match is found or the whole list has been searched. Linear search runs at worst linear time and makes at most n comparison where n is the length of the list.

Binary search also known as half-interval-search, logarithmic search. In binary search compare the target value to the middle element of the array. If they are not equal, the half in which target cannot lie is eliminate and the search continue on the remaining half again taking the middle element to compare to the target value and repeated this until the target value is found. Binary search runs in logarithmic time in the worst case, making o(logn) comparison.

Python Code

l =[1, 2, 3, 4, 0, -1, -22, -11, -19, -220, 100]
ll = sorted(l) # sorting is expensive
v = 10
i1 = 0
i2 = len(ll)

c=0
while True:
    m = int((i1+i2)/2)
    print(f"i1: {i1}, m: {m}, i2: {i2}, ll: {ll}")

    if ll[m] == v:
        print(f"{v} found in {m}")
        break
    elif m==i2 or m==i1:
        print(f"{v} is not in the list.")
        break
    else:
        if ll[m]<v:
            i1=m
        else:
            i2=m

Iteration 1

We select the middle element i.e 0 since, 100 is greater than 0 so we divide the array into two halves and consider the subarray after element 0. Now the new array is 0 1 2 3 4 100

Iteration 2

Select the middle element now it is 3 since, 100 is greater than 3 so we again subdivide the array into two subarray after 3. Now new array is 3 4 100

Iteration 3

Now Select the middle element from the new array which is 4 since 100 is greater than 4 so we subdivide that array intwo subarray. We select the array after 4 now subarray become 100

Iteration

Now there are only one element we compare target element with that element both are equal so we find 100 at the 10th position.

When it is run,

[-220, -22, -19, -11, -1, 0, 1, 2, 3, 4, 100]
i1: 0, m: 5, i2: 11, ll: [-220, -22, -19, -11, -1, 0, 1, 2, 3, 4, 100]
i1: 5, m: 8, i2: 11, ll: [-220, -22, -19, -11, -1, 0, 1, 2, 3, 4, 100]
i1: 8, m: 9, i2: 11, ll: [-220, -22, -19, -11, -1, 0, 1, 2, 3, 4, 100]
i1: 9, m: 10, i2: 11, ll: [-220, -22, -19, -11, -1, 0, 1, 2, 3, 4, 100]
100 found in 10

Day 43 Of #100DaysOfCode and #Python
* Learned More About algorithm
* Linear Search
* Binary Search#WomenWhoCode ,#CodeNewbie #100DaysOfCode #womenintech ,#beginner ,#DEVCommunity ,#pythonprogramming ,#Python3 pic.twitter.com/g81Wk0OYOo

— Durga Pokharel (@mathdurga) February 5, 2021