Python Practice Hashing Binary Search

In this class, we do Python Practice Hashing Binary Search.

For Complete YouTube Video: Click Here

Binary Search Example

The reader should have basic knowledge of Data structures and python.

Check our data structures course for all the related concepts.

For python, Click here.

All these examples will help you improve your coding skill so that you can easily crack placement exams.

consider the following binary search code given below

num_list=[3,6,7,9,15,20]
element=17

How many iterations needed to search given element

def binarysearch(num_list,element):
    low=0
    high=len(num_list)-1
    mid = (low + high)//2
    while(low<=high):
        if(element==numlist[mid]):
            break
        elif(element>num_list[mid]):
            low=mid+1
        else:
            high=mid-1
        mid= (low+high)//2
    if(element=num_list[mid]):
        print("element is at index position",mid)
    else:
        print("element not there in the list")

Output:
3

In the above program, it was given binary search code using loops.

Given an element and how many iterations are done to check the presence of element in the list?

Logic

Binary search checks the middle element in the list.

If the element to be searched is greater than the element in the mid position. The next iteration will search in the right half.

Otherwise, search in the left half.

This search is repeated until low less than or equal to high.

Low is starting position of the partition, and high is the ending position of the partition.

In our example, element 17 has to be searched. The element is not present in the list.

Output: Three iterations.

Hashing example

Which of the follwing hash functions will lead to least number of collisions.
when the following elements are inserted in hash table.

48,98,34,25,18


1) H(key) = Key%8
2) H(Key) = Key%10
3) H(Key) = key%9
4) H(key) = key%3

In the above example, hash keys are given.

The list of elements takes the position by using the hash key.

Example:

Element 48 will take the position 0. because 48%8=0.

If two elements take the same position, a collision occurs.

Check the collision for all the values.

Output: Using key-value nine, we are getting a fewer number of collisions.