DEV Community

Cover image for Learning Python- Basic course: Day 12, Basic algorithms
Aatmaj
Aatmaj

Posted on • Updated on

Learning Python- Basic course: Day 12, Basic algorithms

Today let us explore Sequential search, Binary search and Bubble sort in Python.🚀


Today we will check out sequential search, binary search and bubble sort in Python lists. We will not go into the mathematical details of the complexity and all but just see how the algorithms are implemented. More complicated searching and sorting algorithms, complex data structures will be referenced and covered in the later parts. In case anyone among you are coming across these algorithms for the first time, please do google these terms out. I have also provided Geeksforgeeks references for further reading.

Sequential search

The sequential search is the most easy and simple program for searching. We can just traverse through the list or use the inbuilt in method.

a=[1,3,4,6,5,2,6]
n=int(input("Please enter the number to be searched "))
#Method-1
for i in range(len(a)):
    if (a[i]==n):
        print("Method-1 Yes, the number is in the list ")
        break

#Method-2
if(n in a):
    print("Method-2 Yes, the number is in the list ")
Enter fullscreen mode Exit fullscreen mode

Output

Please enter the number to be searched 6
Method-1 Yes, the number is in the list 
Method-2 Yes, the number is in the list 
Enter fullscreen mode Exit fullscreen mode

Python provides a shortcut for searching as shown in method 2. This is a sequential search method for searching. It can search not only numbers, but characters or any other data types as well.

Binary search

Binary search is another simple algorithm to search for numbers in a sorted list. In case you are new with Binary search, see GeeksForGeeks

a=[1,3,5,6,8,7,10,12,14]
x=int(input("Please enter a number "))
low = 0
high = len(a) - 1
mid = 0
while low <= high:
        mid = (high + low) // 2
        # If x is greater, ignore left half
        if (a[mid] < x):
            low = mid + 1
        # If x is smaller, ignore right half
        elif (a[mid] > x):
            high = mid - 1
        # means x is present at mid
        else:
            print(mid+1)
            break     
Enter fullscreen mode Exit fullscreen mode

Output-

Please enter a number 6
4
Enter fullscreen mode Exit fullscreen mode

Bubble sort

Bubble sort is a good sorting algorithm, and quite easy comparatively. more about it on GeeksForGeeks

a=[2,4,3,7,6,5,9,10,12]
 # Traverse through all array elements
for i in range(len(a)):
    # Last i elements are already in place
    for j in range(0, len(a)-i-1):
            # traverse the array from 0 to n-i-1
            # Swap if the element found is greater
            # than the next element
            if (a[j] > a[j+1]) :
                (a[j], a[j+1]) = (a[j+1], a[j]) #Swapping the two

print ("Sorted array is:",a)
Enter fullscreen mode Exit fullscreen mode

Output-

Sorted array is: [2, 3, 4, 5, 6, 7, 9, 10, 12]
Enter fullscreen mode Exit fullscreen mode

Exercises-

1) & 2) In the samples above, the programs give no output if the item is not in the list. Modify the programs to include it. Answers - Sequential search, binary search

3) Write a program to bubble sort a list and then search using binary search. Answer


😎 Your suggestions motivate me, so please please please let me know in the comment section if you this part or not. 🧐 And don't forget to like the post if you did. 😍 Follow me on github and star the Learning-Python repo

Discussion (1)

Collapse
ayabouchiha profile image
Aya Bouchiha

Amazing post!