life is short - you need Python!

Count frequency of items in a list using Python

2021-05-01T06:40:00.003+06:00

In this post I am going to show you how we can write a program in Python that can count the frequency of items in a list. First I shall implement it using the dictionary data structure in Python. Then I shall make it shorter (and nicer) using the defaultdict and Counter data structures from the collections module.

Here is our code that we will use to run and test the program -

if __name__ == "__main__":
    li = [2, 6, 9, 2, 8, 2, 9, 9, 3, 1, 4, 5, 7, 1, 8, 10, 2, 10, 10, 5]
    freq = frequency_counter(li)
    assert freq[1] == 2
    assert freq[2] == 4
    assert freq[3] == 1
    assert freq[11] == 0

Now let's look at the implementation using dictionary. We will iterate over all the items and then check if it exists in the dictionary. If it exists, we shall increase the count. And if it doesn't, then we shall set the count to 1.

def frequency_counter(li):
    freq_dt = dict()
    for item in li:
        if item in freq_dt:
            freq_dt[item] += 1
        else:
            freq_dt[item] = 1

    return freq_dt

defaultdict is a data sturcture very similar to dictionary (actually it extends the dictionary). The advantage is, you can create the dictionary using a default type, so when an item is not in the dictionary yet, the zero value of the default type would be used. Say 5 doesn't exist in the dictionary, the dt[5] would return 0. That's a huge convenience.

def frequency_counter(li):
    freq_dt = defaultdict(int)
    for item in li:
        freq_dt[item] += 1

    return freq_dt

Now let me introduce Counter, a special purpose dictionary. Instead of writing anything, showing code would be the best way -

def frequency_counter(li):
    freq_dt = Counter(li)
    return freq_dt

You can find the code here.

Python Program to Find Prime Factors of a Number

2021-04-27T18:41:00.003+06:00

In this post I am going to write a program in python that finds all the prime factors of a number. I am going to start by writing an empty function and a test.

  def get_prime_factors(number):
      prime_factors = []
      return prime_factors
      
  if __name__ == "__main__":
      n = 8
      expected = [2, 2, 2] 
      result = get_prime_factors(n)
      assert expected == result, result

Now, if you run the program above, it will give an AssertionError, as we are returning an empty list. Let's write some code to make our test pass.

    def get_prime_factors(number):
        prime_factors = []
        
        while number % 2 == 0:
            prime_factors.append(2)
            number = number // 2
            
        return prime_factors

The program will work for multiple of 2's. Our next task is to find the other prime factors. For example, prime factors of 10 are 2 and 5. We shall add this test case first and then write code to pass this test. If you have studied prime numbers before, then you might remember that if the number itself is not prime, then you will find all the prime factors in the range from 2 to square root of n. So we shall use a loop to try every number upto square root of n to check if that number is a factor of n. And as we already tried to divide the number by 2, we can try only odd numbers.

    from math import sqrt
    
    def get_prime_factors(number):
        prime_factors = []
        
        while number % 2 == 0:
            prime_factors.append(2)
            number = number // 2
            
        sq_root = int(sqrt(number))
        for m in range(3, sq_root+1, 2):
            if number % m == 0:
                prime_factors.append(m)
                number = number // m
                
        return prime_factors

We made some good progress. However, the get_prime_factors function above won't pass the test case for 10. Because in the first while loop, number is divisible by 2, so we shall add 2 to the list of prime factors. Then we divide the number by 2, so it becomes 5 (10 // 2). And the value of sq_root is 2, so the value of m in the for loop will be 3 (for m in range(3, 3, 2)). So we didn't get anything out of that loop. Because here 5 itself is a prime number. So after the for loop, we need to check if number is still greater than 1. And if it is, then we can safely assume that it's a prime number (and a prime factor of number), thus add to our list of prime factors. If you spend some time, you will be able to complete the code by yourself. And don't forget to test the code with different values of n (1, 2, 4, 5, 25, 100, 101). I hope you found it useful.

You can find the full code here.

divmod - division and modulus together in Python

2018-10-11T16:47:00.000+06:00

divmod is a wonderful, nice, little built-in function in Python that allows you to do division and modulus operation together. Using it, you can make your code slightly beautiful, thus Pythonic! Check the following example -

>>> 10 / 3
3.3333333333333335
>>> 10 // 3
3
>>> 10 % 3
1
>>> divmod(10, 3)
(3, 1)

Python all any built-in function

2018-09-16T20:52:00.002+06:00

I have been using Python for a long time, still learning lot of simple and new things. Recently I came to know about two built-in functions named all and any. Today while I was solving a hackerrank problem, I used both functions which makes the code a bit nicer, in my opinion.

The functions compares two singly linked lists and if they are equal, returns 1, otherwise returns 0. Here is my code -

def compare_lists(llist1, llist2):
    while all([llist1, llist2]):
        if llist1.data != llist2.data:
            return 0
        llist1 = llist1.next
        llist2 = llist2.next
        
    if any([llist1, llist2]):
        return 0
    
    return 1

Sometimes, this kind of simple thing brings joy to me. Let me know your thoughts. :)

Create 2D Array using List in Python

2018-04-10T12:45:00.000+06:00

If for some reason you want to create a two dimensional array in Python and don't want to use external packages like numpy etc., the most obvious thing is to write a code like this :

>>> n = 3
>>> m = 4
>>> ara = [[0] * m] * n
>>> ara
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

But there is a problem. Check the code below-

>>> ara[0][0] = 1
>>> ara
[[1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]]

Actually, when you do [0] * m, it returns a reference to a list and when you multiply it with n, the same reference is duplicated. Hence you see the change in a way that you didn't expect.

The right way to do it is to append [0] * m, n times in the array. You can code it in multiple ways. My preferred way is:

>>> ara = [[0] * m for _ in range(n)]

Table Driven Unit Test in Python

2017-10-29T10:33:00.004+06:00

Now days, table driven tests are pretty much industry standard. In my workplace, we use table driven tests when we write unit tests (in golang though). Here I shall share a simple code example using pytest that shows how to write table driven tests in Python.

In table driven test, what you need to do is, to gather all the tests cases together in a single table. We can use dictionary for each test case and a list to store all the test cases. Instead of discussing it further, let me show you an example :

def average(L):
    if not L:
        return None
    return sum(L)/len(L)

def test_average():
    test_cases = [
        {
            "name": "simple case 1",
            "input": [1, 2, 3],
            "expected": 2.0
        },
        {
            "name": "simple case 2",
            "input": [1, 2, 3, 4],
            "expected": 2.5
        },
        {
            "name": "list with one item",
            "input": [100],
            "expected": 100.0
        },
        {
            "name": "empty list",
            "input": [],
            "expected": None
        }
    ]

    for test_case in test_cases:
        assert test_case["expected"] == average(test_case["input"]), test_case["name"]

Now if you run the test, you will get the following output :

$ pytest average.py

==================== test session starts =====================

platform darwin -- Python 3.5.1, pytest-3.0.3, py-1.4.31, pluggy-0.4.0

rootdir: /Users/tamimshahriar/..., inifile:

collected 1 items

average.py .

================== 1 passed in 0.01 seconds ==================

Hope you will find this post useful and use table driven tests. :)

global and nonlocal variable in Python

2017-06-13T00:20:00.004+06:00

Most of us are already familiar with global variables in Python. If we declare those variables in a module, the functions inside that module (can read python file or .py file) can access the variable. For example, check the code below :

x = 5

def myfnc():
print("inside myfnc", x)
def myfnc2():
print("inside myfnc2", x)

myfnc2()

myfnc()

It will print :
inside myfnc 5
inside myfnc2 5

If you change your code like this :

x = 5

def myfnc():
print("inside myfnc", x)
def myfnc2():
print("inside myfnc2", x)
x = 10
print("x = ", x)

myfnc2()

myfnc()

You will get an error :

File "program.py", line 6, in myfnc2
print("inside myfnc2", x)
UnboundLocalError: local variable 'x' referenced before assignment

The moment you wrote x = 10, Python assume that x is a local variable, and inside the print function, it is giving this error. Because local variables are determined at compile time (from official doc : "local variables are already determined statically"). You can get rid of the error, if you declare x as global.

x = 5

def myfnc():
print("inside myfnc", x)
def myfnc2():
global x
print("inside myfnc2", x)
x = 10
print("x = ", x)

myfnc2()

myfnc()

Now you can run the program again. It won't throw any error. What if we code like this now?

x = 5

def myfnc():
print("inside myfnc", x)
y = 10
def myfnc2():
global x
print("inside myfnc2", x, y)
x = 10
print("x = ", x)

myfnc2()

myfnc()

If you run the program, you will see desired output. But now, if you want to write to y inside myfnc2() (for example, assign something like y = 1), you can't use global y, as y is not a global variable. You can try this following code that fails successfully :

x = 5

def myfnc():

print("inside myfnc", x)

y = 10

def myfnc2():

global x

global y

print("inside myfnc2", x, y)

x = 10

print("x = ", x)

y = 1

print("y = ", y)

myfnc2()

myfnc()

You will get this error : NameError: name 'y' is not defined

We need to understand that, y is not a global variable. Here nonlocal can help! Instead of global y, just write nonlocal. It will make y available and writable inside myfnc2().

x = 5

def myfnc():

print("inside myfnc", x)

y = 10

def myfnc2():

global x

nonlocal y

print("inside myfnc2", x, y)

x = 10

print("x = ", x)

y = 1

print("y = ", y)

myfnc2()

myfnc()

This is something I learnt today. :)

Python Code Measure Time

2017-01-08T09:14:00.002+06:00

How to measure time of a Python code snippet?

We can do it using the timeit module. It has a function called timeit that runs a particular code snippet for N times (one million by default) and gives you the runtime. Today I just used it for a small purpose and thought of writing a note here.

>>> from timeit import timeit
>>> timeit('"c" >= "a" and "c" <= "z"')
0.06282545300200582
>>> timeit('"c".isalpha()')
0.06563570606522262

Here I compared the performance between two snippets : one uses isalpha() to determine if a (lowercase) character is an alphabet or not, another just compares using operators. There is no noticeable performance difference. Please go through the module doc to get some more ideas of how to use the timeit module, if will often come handy when you quickly want to measure running time of different Python code.

Code School Python Courses

2016-02-03T23:19:00.000+06:00

As Python is getting more and more popular and becoming the de facto standard for starting to learn programming, we can see increasing amount of online content to learn Python. Last week got an email form Code School team to check out their couple of new Python courses. I spent around 30 minutes watching the videos, checkout out the exercises. The exercises are good, and can be done online. They also prepared the videos with care. But one thing that bothers me, the lecture is kind of robotic. I didn't feel anything special, in fact didn't feel the connection to the teacher that I used to feel in other courses in Coursera and Udacity. Anyway, Python beginners can check those courses:
1. Try Python
2. Flying through Python

How to get image size from url

2015-02-25T16:43:00.002+06:00

Today I needed to get image size (width and height) from image urls. I am sharing my python code here.

import requests
from PIL import Image
from io import BytesIO


def get_image_size(url):
    data = requests.get(url).content
    im = Image.open(BytesIO(data))    
    return im.size


if __name__ == "__main__":
    url = "https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgQiI_ipTLsmwY5rfnlGkMdp0Bq2bwLmlhtXRuQMJjCYxojb1bxaZ-LRGdiMlP0XiBWlgG0HCF3GbHQAlrMVi16isP7lwWhBySdTtipnnuWk6UrYiztsKtwStN_0-pyR_mlnMbt9_5rCx14/s1600/sbn_pic_2.jpg"
    width, height = get_image_size(url)
    print width, height

I used pillow - which is a PIL fork.

Feel free to comment if you have any suggestion to improve my code.

crawler controller

2015-01-13T11:37:00.000+06:00

I work on a project where I have written 20+ crawlers and the crawlers are running 24/7 (with good amount of sleep). Sometimes, I need to update / restart the server. Then I have to start all the crawlers again. So, I have written a script that will control all the crawlers. It will first check if the crawler is already running, and if not, then it will start the crawler and the crawler will run in the background. I also saved the pid of all the crawlers in a text file so that I can kill a particular crawler immediately when needed.

Here is my code :

import shlex
from subprocess import Popen, PIPE

site_dt = {'Site1 Name' : ['site1_crawler.py', 'site1_crawler.out'],

'Site2 Name' : ['site2_crawler.py', 'site2_crawler.out']}

location = "/home/crawler/"

pidfp = open('pid.txt', 'w')


def is_running(pname):
    p1 = Popen(["ps", "ax"], stdout=PIPE)
    p2 = Popen(["grep", pname], stdin=p1.stdout, stdout=PIPE)
    p1.stdout.close()  # Allow p1 to receive a SIGPIPE if p2 exits.
    output = p2.communicate()[0]
    if output.find('/home/crawler/'+pname) > -1:
        return True
    return False


def main():
    for item in site_dt.keys():
        print item
        if is_running(site_dt[item][0]) is True:
            print site_dt[item][0], "already running"
            continue
        cmd = "python " + location + site_dt[item][0] + " -l info"   
        outfile = "log/" + site_dt[item][1] 
        fp = open(outfile, 'w')
        
        pid = Popen(shlex.split(cmd), stdout=fp).pid
        
        print pid
        print
        pidfp.write(item + ": " + pid + "\n")
        
    pidfp.close()
    
    
if __name__ == "__main__":
    main()

If you feel that there is scope for improvement, please comment.

finding maximum element of a list - divide and conquer approach

2015-01-09T16:01:00.001+06:00

Here I share my Python implementation of divide and conquer approach of finding maximum element from a list :

"""
Divide and conquer approach to find the maximum from a list
"""

def find_max(li, left, right):
    if left == right:
        return li[left]
    mid = (left + right) / 2
    max1 = find_max(li, left, mid)
    max2 = find_max(li, mid+1, right)
    return max1 if max1 > max2 else max2
    
    
def main():
    li = [1, 5, 2, 9, 3, 7, 5, 2, 10]
    print "Maximum element of the list is", find_max(li, 0, len(li)-1)
    
    
if __name__ == "__main__":
    main()

pow() function returns float or integer?

2014-12-06T23:39:00.002+06:00

Today, someone posted this code and asked why x is float ?

>>> from math import pow
>>> x = pow(5, 2)
>>> x
25.0

It's float because the pow function of math package returns float. But there is a built-in pow function in Python which will return integer in this case. You need to restart the python interpreter before you run the following code :

>>> a = 5
>>> x = pow(a, 2)
>>> x
25
>>> type(x)
<type 'int'>

So, don't get confused. Happy coding! :)

AttributeError: 'module' object has no attribute

2014-11-11T19:59:00.000+06:00

Are you getting this type of error in your Python program?

AttributeError: 'module' object has no attribute 'whatever' ?

Well, then you might need to change the name of your python file.

For example, save the following code in a file named json.py :

 
import json

print json.dumps(['foo', {'bar': ('baz', None, 1.0, 2)}])

Then try to run it, and you will get this error :

$ python json.py

Traceback (most recent call last):
  File "json.py", line 1, in 
    import json
  File "/home/work/practice/json.py", line 3, in 
    print json.dumps(['foo', {'bar': ('baz', None, 1.0, 2)}])
AttributeError: 'module' object has no attribute 'dumps'

But of course the json module has 'dumps' attribute! What went wrong?

When you wrote import json, it tries to find the file json.py in the current directory first and it got the file that you wrote (you saved the file as json.py) and it surely doesn't have any attribute (variable or method) named dumps. All you need to do is to change your filename.

So, the lesson is, don't name your python program such a way that it matches a module name used in your program. Happy coding. :)

How to empty a list

2014-10-29T18:48:00.001+06:00

Say you have a list in your program and you are going to reuse the name of the list, or delete all items from the list (empty the list). One option is to delete the list completely along with the name :

>>> del li

Another option is to delete all items inside the list:

>>> del li[:]

Many of you can think of another alternative :

>>> li = []

Though li = [], apparently it makes li empty, actually it is creating a new list object and the previous object will be in memory.

Now, if you take some time to play in your Python interpreter, you will have a better idea what happens :

>>> li = [1, 2, 3, 4, 5]
>>> li2 = li
>>> li2
[1, 2, 3, 4, 5]
>>> del li[:]
>>> li
[]
>>> li2
[]
>>> li1 = [1, 3, 5]
>>> li3 = li1
>>> li3
[1, 3, 5]
>>> li1
[1, 3, 5]
>>> li1 = []
>>> li1
[]
>>> li3
[1, 3, 5]
>>> li4 = [1, 2]
>>> li5 = li4
>>> li5
[1, 2]
>>> del li4
>>> li4
Traceback (most recent call last):
File "", line 1, in
NameError: name 'li4' is not defined
>>> li5
[1, 2]
>>>

fastest list index searching

2014-08-28T07:04:00.002+06:00

Someone was looking for fastest list index searching (in Python) in stackoverflow. There are only four elements in the list, still it was as issue for him, as it was used in an inner-loop and the profiler identified that, this part was executing the most. He tried several approaches.

1. This is the most obvious one:

if value in mylist:
    return mylist.index(value)

Here the problem is, in the condition used in if, it takes O(n) time to check if the value is in the list, and the return statement - mylist.index(value), also takes O(n) time.

2. The second approach - I call it smart approach :

try:
    return mylist.index(value)
except ValueError:
    return None

This code gets rid of the condition check. But the try-except thing takes some time for the Python interpreter. I like this approach. In fact, if the list was large, I would prefer this.

3. The third approach - I guess it's more Pythonic?

for i, x in enumerate(mylist):
    if x == value:
         return i
return None

All the above solutions are OK. But he was looking for the fastest way. So, I gave the solution :

 if value == mylist[0]:
   return 0
 elif value == mylist[1]:
   return 1
 elif value == mylist[2]:
   return 2
 elif value == mylist [3]:
   return 3

Yes, it is the fastest among the discussed options. And he happily accepted the solution. :)

Here you can find the post : stackoverflow.com/questions/25476179/fastest-list-index-searching/

Python video tutorials in Bangla

2014-08-20T20:07:00.001+06:00

Finally, I have completed my video tutorial series on Python. The lectures are given in my native language - Bangla (Bengali). Click here to check the videos.

In the course I assume that the student has prior programming experience in C / Java. So this is not suitable for programming beginners, rather it's suitable for Python beginners.

There are six units in the series and each unit has several videos (8 to 12). The topics covered are : Introduction to Python, Variables, Conditional Logic, Loop, Data Structures (List, Dict, Set, Tuple), Input/Output, File, Exception Handling, Modules and Packages, Object Oriented Programming, Iterators, Generators etc. I couldn't make it a complete course because I didn't have time to prepare assignments, quizzes, questions. Hope, I can offer a full course online via +Dimik Computing School in future on Python.

Python list of lists

2014-08-09T23:16:00.000+06:00

I just stumbled upon a post/problem in stackoverflow. Here I discuss it and the solution.

First check the following code segment :

>>>visited = [[False]*4]*4
>>>visited[0][1] = True
>>>print visited
>>> [[False, True, False, False], [False, True, False, False], [False, True, False, False], [False, True, False, False]]

Do you see the problem, second element of all the list changed to True! So it means [[False]*4]*4 creates a list that contains reference to the same list [False, False, False, False]

You can avoid this by following this code:

    >>> n = 4
    >>> m = 4
    >>> visited = []
    >>> for x in xrange(n):
    ...      visited.append([False] * m)
    ... 
    >>> visited
    [[False, False, False, False], [False, False, False, False], [False, False, False, False], [False, False, False, False]]
    >>> visited[0][1] = True
    >>> visited
    [[False, True, False, False], [False, False, False, False], [False, False, False, False], [False, False, False, False]]
    >>>

turtle triangle fun

2014-07-27T21:33:00.005+06:00

Just Wrote this piece of code. First just copy-paste the code, run and have fun. Then try to write it yourself and have more fun. :)

import turtle

def draw_triangle(side_length, depth):
    if depth == 0:
        return
    
    counter = 0
    while counter < 3:
        counter += 1
        brad.forward(side_length/2)
        if depth > 1:
            brad.left(120)
        draw_triangle(side_length/2, depth-1)
        brad.forward(side_length/2)
        
        brad.right(120)
        
    brad.left(240)
    
    

if __name__ == "__main__":
    window = turtle.Screen()
    window.bgcolor("white")
    
    brad = turtle.Turtle()
    brad.shape("turtle")
    brad.color("green", "green")
    brad.speed(5)
    
    brad.begin_fill()
    brad.right(120)
    brad.forward(128)
    brad.left(120)
    brad.forward(256)
    brad.left(120)
    brad.forward(256)
    brad.left(120)
    brad.forward(128)
    brad.left(120)
    brad.end_fill()
    brad.color("green", "white")
    brad.begin_fill()
    draw_triangle(128, 3)
    brad.end_fill()
    
    window.exitonclick()

draw circle using squares

2014-07-18T20:52:00.000+06:00

I am checking out a Python course at udacity and found an interesting Python module named Turtle. Now let me share with you a simple code that I just have written.

import turtle

def draw_square():
    window = turtle.Screen()
    window.bgcolor("red")
    
    brad = turtle.Turtle()
    brad.shape("turtle")
    brad.color("yellow")
    brad.speed(5)
    counter = 0
    while counter < 36:
        brad.forward(100)
        brad.right(90)
        brad.forward(100)
        brad.right(90)
        brad.forward(100)
        brad.right(90)
        brad.forward(100)
        brad.right(100)
        counter += 1

    window.exitonclick()

if __name__ == "__main__":
    draw_square()

Just save the code in a file and run it, and you will see something like this:

Now a simple question for you. How did I come up with the number 36 in the while loop? (while counter < 36).

Heap Sort Implementation in Python

2013-11-01T18:14:00.003+06:00

Here I share my Python implementation of heap sort algorithm. Heap sort is O(n log n) sorting algorithm though quicksort is used more frequently. You should learn heap sort to implement priority queue or at least learn the internals of priority queue. :)

In the Python code, I directly followed the heap sort algorithm presented in Introduction to Algorithms by CLRS.

# heapsort

def max_heapify(li, i, heap_size):
  l = i * 2 #left(i)
  r = l + 1 #right(i)
  if l <= heap_size and li[l] > li[i]:
    largest = l
  else:
    largest = i
  if r <= heap_size and li[r] > li[largest]:
    largest = r
  if i != largest:
    li[i], li[largest] = li[largest], li[i]
    max_heapify(li, largest, heap_size)

def build_max_heap(li, heap_size):
  for i in range(heap_size/2 - 1, 0, -1):
    max_heapify(li, i, heap_size) 

def heap_sort(li, heap_size):
  build_max_heap(li, heap_size)
  for i in range(len(li[1:]), 1, -1):
    li[1], li[i] = li[i], li[1]
    heap_size = heap_size - 1
    max_heapify(li, 1, heap_size)

def main():
  # we shall consider the list from element 1, not 0
  li = [0, 16, 4, 10, 14, 7, 9, 3, 2, 8, 1]
  heap_size = len(li[1:])
  heap_sort(li, heap_size)
  print li[1:]

if __name__ == "__main__":
  main()

Merge Sort Implementation in Python

2013-10-20T15:14:00.001+06:00

Today I post the python implementation of merge sort. This is straight-forward implementation of the algorithm presented in the book Introduction to Algorithms [CLRS]. If you think the implementation can be more Pythonic, feel free to comment.

Here is my code:

def merge(li, start, mid, end):
  left_li = []
  left_li.extend(li[start : mid+1])
  right_li = []
  right_li.extend(li[mid+1: end+1])
  left_li.append(2147483647)
  right_li.append(2147483647)
  i = 0
  j = 0
  for k in range(start, end+1):
    if left_li[i] <= right_li[j]:
      li[k] = left_li[i]
      i += 1
    else:
      li[k] = right_li[j]
      j += 1


def merge_sort(li, start, end):
  if start < end:
    mid = (start + end) / 2
    merge_sort(li, start, mid)
    merge_sort(li, mid+1, end)
    merge(li, start, mid, end)

if __name__ == "__main__": 
  li = [5, 2, 4, 7, 1, 3, 2, 6, -4]
  print li
  merge_sort(li, 0, len(li)-1)
  print li

You can test the merge sort implementation against this problem: http://www.spoj.com/problems/MERGSORT/

recursive binary search in python

2013-10-16T01:09:00.002+06:00

In my previous post, I showed the iterative way to implement binary search algorithm in Python. Here comes the recursive way.

def binary_search_recursive(li, left, right, key):
  while True:
    if left > right:
      return -1
    mid = (left + right) / 2
    if li[mid] == key:
      return mid
    if li[mid] > key:
      right = mid - 1
    else:
      left = mid + 1
    return binary_search_recursive(li, left, right, key)

if __name__ == "__main__":
  li = [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12]
  left = 0
  right = len(li)
  for key in  [8, 6, 1, 12, 7]:
    index = binary_search_recursive(li, left, right, key)
    print key, index

iterative binary search in python

2013-10-16T01:06:00.002+06:00

Today I am going to post the code for binary search. This one is iterative and the next one will be recursive. If you don't know about binary search, please read the wikipedia article first.

Now, here is my Python implementation of binary search algorithm:

def binary_search_iterative(li, left, right, key):
  while True:
    if left > right:
      return -1
    mid = (left + right) / 2
    if li[mid] == key:
      return mid
    if li[mid] > key:
      right = mid - 1
    else:
      left = mid + 1

if __name__ == "__main__":
  li = [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12]
  left = 0
  right = len(li)
  for key in  [8, 6, 1, 12, 7]:
    index = binary_search_iterative(li, left, right, key)
    print key, index

insertion sort implementation in python

2013-10-15T01:00:00.001+06:00

I am working on my Python coding skills and this time reviewing various algorithms with which I have not been in touch for many days. So I start with sorting, here is my code for insertion sort:

def insertion_sort(ara):
    for j in range(1, len(ara)):
        key = ara[j]
        i = j - 1
        while i >= 0 and key < ara[i]:
            ara[i+1] = ara[i]
            i -= 1
        ara[i+1] = key

    return ara

if __name__ == "__main__":
    ara = [10, 5, 2, 9, 4, 8, 9, 2, 1]
    print insertion_sort(ara)

More python implementation of various algorithms are coming soon. Meanwhile if you feel that there is chance to improve my code, or make it more pythonic, please feel free to comment.

Oh, if you are not familiar with algorithms yet and wording what the ... is insertion sort, please visit the wikipedia article on insertion sort.