0

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

Improve this question
5
  • 2
    The Pythonic way is the answer to the linked question. Commented Mar 15, 2016 at 17:01
  • Also, see the bisect source. Commented Mar 15, 2016 at 17:05
  • User also asked about even and odd list. my answer covers that. Commented Mar 15, 2016 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. Commented Mar 15, 2016 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. Commented Mar 15, 2016 at 18:33

1 Answer 1

Reset to default
1

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
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

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.