Binary Search Algorithm

Atebar Haider — Tue, 29 Sep 2020 14:52:14 +0000

Binary search algorithm is an efficient algorithm that searches a sorted list for a desired or target element.

Binary search works by comparing the target value to the middle element of the list.
If the target value is greater than the middle element, the left half of the list is eliminated from the search space, and the search continues in the right half.

If the target value is less than the middle value, the right half is eliminated from the search space, and the search continues in the left half.

This process is repeated until the middle element is equal to the target value, or if the algorithm returns that the element is not in the list at all.

The Worst Case Time Complexity is O(log n)

Algorithm:

The variable start is set to 0 and end is set to the length of the list.
The variable start keeps track of the first element in the part of the list being searched while end keeps track of the element one after the end of the part being searched.
A while loop is created that iterates as long as start is less than end.
mid is calculated as the floor of the average of start and end.
If the element at index mid is less than key (i.e. desired element) then start is set to mid + 1.
If it is larger than key then end is set to mid.
Otherwise, the element at mid index will be equal to key which is returned as the index of the found element.
If no such item is found, -1 is returned.

Let's take an example, suppose we have following list:

List_Item	21	23	24	35	45	48	56	77	89
Index	0	1	2	3	4	5	6	7	8

And we want search if 24 is present in the list or not.

According to the algorithm we need to set some variables
start = 0 (index of first element)
end = 8 (index of last element)
mid = 4 = (0+8)/2 (index of middle element)

List_Item	21	23	24	35	45	48	56	77	89
Index	0	1	2	3	4	5	6	7	8
Positions	start				mid				end

Now we will arrange the variables according to current value of mid index i.e 48
If the element at index mid (i.e. 48 ) is less than 24 then start is set to mid + 1
And if the element at index mid (i.e.48) is larger than 24 then end is set to mid
Otherwise, the element at mid index will be equal to 24 which is returned as the index of the found element.

We can clearly see that 24 < list[mid], so we will make following changes.
start = 0 no changes
end = 4 current mid
mid = 2 = (0+4) / 2

List_Item	21	23	24	35	45	48	56	77	89
Index	0	1	2	3	4	5	6	7	8
Positions	start		mid		end

We will repeat this process until start < end. If start goes to less than end that mean element is not present in the list.

Now if we analyze the current positions of variable, we can clearly that 24 is equal to value of mid index. We will return this index.

Following is the implementaion of binary search algorithm in Python

def binary_search(mylist, key):
    """Search key in mylist [start... end - 1]."""
    start = 0
    end = len(mylist)
    while start < end:
        mid = (start + end)//2
        if mylist [mid] > key:
            end = mid
        elif mylist [mid] < key:
            start = mid + 1
        else:
            return mid
    return -1


mylist = input[21, 23, 24, 35, 45, 48, 56, 77, 89]
key = 24

index = binary_search(mylist, key)
if index < 0:
    print(key ,' was not found.’)
else:
    print(key , 'was found at index', index)

OUTPUT:

24 was found at index 2.

Sieve of Eratosthenes Algorithm to find Prime Number

Atebar Haider — Mon, 28 Sep 2020 04:16:34 +0000

Sieve of Eratosthenes is a simple and ancient algorithm used to find the prime numbers up to any given limit. It is one of the most efficient ways to find small prime numbers.

For a given upper limit n the algorithm works by iteratively marking the multiples of primes as composite, starting from 2. Once all multiples of 2 have been marked composite, the multiples of next prime, i.e. 3 are marked composite. This process continues until p*p ≤ n where p is the current prime number.

Following is the algorithm of Sieve of Eratosthenes to find prime numbers.

1. To find out all primes under n, generate a list of all integers from 2 to n.

(Note: 1 is not a prime number)

2. Start with a smallest prime number, i.e. p = 2
3. Mark all the multiples of p which are less than n as composite. To do this, we will mark the number as 0. (Do not mark p itself as composite.)
4. Assign the value of p to the next non-zero number in the list which is greater than p.
5. Repeat the process until p*p ≤ n

Example: Generate all the primes up to 11

First thing to note is that do not mark prime themselves as composite.
1. Create a list of integers from 2 to 11.

2	3	4	5	6	7	8	9	10	11

2. Start with p=2
3. Since 2*2 ≤ 11, continue.
4. Mark all multiples of 2 as composite by setting their value as 0 in the list.

2	3	0	5	0	7	0	9	0	11

5. Assign the value of p to the next prime, i.e. 3
6. Since 3*3 ≤ 11 , continue.
7. Mark all multiples of 3 as composite by setting their value as 0 in the list.

2	3	0	5	0	7	0	0	0	11

8. Assign the value of p to 5
9. Since 5*5 ≰ 11 so we stop here.
We are done! The list is:

2	3	0	5	0	7	0	0	0	11

Since all the numbers which are 0 are composite, all the non-zero numbers are prime.

Hence the prime numbers up to 11 are 2, 3, 5, 7, 11

Python program to print all primes smaller than or equal to a given limit using Sieve of Eratosthenes.

n = int(input("Enter an integer number:"))
prime = [] # An empty list
for i in range(n+1):
    prime.append(i)

prime[0]=0
prime[1]=0   

p = 2
while (p * p <= n): 
    # If prime[p] is not changed, then it is a prime 
    if (p != 0): 
        # Update all multiples of p to zero
        for i in range(p*2, n+1, p): 
            prime[i] = 0

    p += 1

#print all element of list which are not zero
print("All the prime numbers up to", n, "are:")
for i in range(len(prime)):
    if (prime[i] != 0):
        print(prime[i], end=" ")