Binary search of a number within a list in Python

Question

I was researching about binary search of a number within a list and came across this discussion

Somewhere else I it was mentioned about going for even and odd numbered list separately. But is that language specific? The information is little confusing.

For Binary search , I know high-level I need to carry out following steps,

sort the list in ascending order
Check for middle item within a list if thats the number we are done
if not , if the number is greater than the middle number, get rid of lower half
if searched number is lower than middle number , get rid of uppeer half
keep repeating until number is found

The list can be ascending or descending order and can be of float of int numbers. what's pythonic way of carrying out above pseudocode? I am using python 2.7.x on windows.

** EDIT ** The mentioned discussion does not cover even and odd list (at least I couldn't see any
I would like to request more clarifications on that such as,
- If I need to treat even odd list differently
- Is there a way in python that will take care of that

The Pythonic way is [the answer](http://stackoverflow.com/a/2233940/1084416) to the linked question. — Peter Wood, Mar 15 '16 at 17:01
Also, see [the **`bisect`** source](https://github.com/python-git/python/blob/master/Lib/bisect.py#L67). — Peter Wood, Mar 15 '16 at 17:05
User also asked about `even` and `odd` list. my answer covers that. — Anil_M, Mar 15 '16 at 17:15
@anil_M : Thanks for also covering `even , odd` list part of the question. Will the integer division work for both integers as well as float list. I will try out your code. — , Mar 15 '16 at 18:20
We are dividing number of elements rather than their values (float / int) etc. Hence whether your list has 10 int numbers or 10 float numbers `10 /3 will be still equal to 3`. Also, you will need to replace main function accordingly to generate float list and float random number.Hope this helps. — Anil_M, Mar 15 '16 at 18:33

score 1 · Accepted Answer · answered Mar 15 '16 at 17:14

Apart from bisect and ( as listed in discussion) you can create your own function. Below is a possible way this can be done.

If you use integer division within python , it will take care of even / odd list. As an e.g. 10 / 3 = 3 and 9 / 3 = 3.

Sample Code

import random
def binarySearch(alist, item):
        first = 0
        last = len(alist) - 1
        found = False

        while first<=last and not found:
            midpoint = (first + last)//2            
            if alist[midpoint] == item:
                found = True
            else:
                if item < alist[midpoint]:
                    last = midpoint-1
                else:
                    first = midpoint+1  
        return found

def findThisNum(mynum):

    testlist = [x for x in range(listlength)]

    print "testlist = ", testlist
    print "finding number ", mynum

    if (binarySearch(testlist, findnum)) == True:
        print "found %d" %mynum
    else:
        print "Not found %d" %mynum




#### Main_Function ####

if __name__ == "__main__":
    #

    #Search 1 [ Even numbered list ]
    listlength = 10    
    findnum = random.randrange(0,listlength)
    findThisNum(findnum)     

    #Search 2 [ [ Odd numbered list ]
    listlength = 13    
    findnum = random.randrange(0,listlength)
    findThisNum(findnum)

    #search 3  [ find item not in the list ]

    listlength = 13    
    findnum = random.randrange(0,listlength) + listlength
    findThisNum(findnum)

Output

Python 2.7.9 (default, Dec 10 2014, 12:24:55) [MSC v.1500 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>> 
testlist =  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
finding number  4
found 4
testlist =  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
finding number  9
found 9
testlist =  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
finding number  21
Not found 21

Hi, the solution works with both even and odd lists as well as float lists. Its easier to understand step by step concept.Tried manual float list for test purpose. - thanks. — , Mar 15 '16 at 20:37

Binary search of a number within a list in Python

1 Answers1