1 Replies - 695 Views - Last Post: 13 August 2012 - 09:11 AM Rate Topic: -----

#1 trigger202  Icon User is offline

  • New D.I.C Head

Reputation: -1
  • View blog
  • Posts: 31
  • Joined: 13-March 11

finding more than one item in a list using binary search

Posted 13 August 2012 - 01:20 AM

this is what i have done but this only locates one item in the list i want to print out both indices of item 36
please help
if the way i posted this or my question isn't clear i apologize in advance

def main():
    
    mylist=[]
    for i in range(20):
        mylist.append(i*3)
    mylist.sort()
    print mylist
    mylist.append(36)
    binarySearch(mylist,0,len(mylist),3)
def binarySearch(thelist,lower,upper,item):
    if upper<lower:
        print 'item not in the list'
        return 
    middle=(lower+upper)/2
    if thelist[middle]<item:
        lower=middle+1
        binarySearch(thelist,lower,upper,item)
    elif thelist[middle]>item:
        upper=middle-1
        binarySearch(thelist,lower,upper,item)
    else: 
        print 'the item was found at index ',middle
        return
    
main()


this is the list generated:[0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 36, 39, 42, 45, 48, 51, 54, 57]
after running the code:
the item was found at index  : 13




This post has been edited by trigger202: 13 August 2012 - 01:22 AM


Is This A Good Question/Topic? 0
  • +

Replies To: finding more than one item in a list using binary search

#2 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 756
  • View blog
  • Posts: 1,990
  • Joined: 23-December 08

Re: finding more than one item in a list using binary search

Posted 13 August 2012 - 09:11 AM

I'm not going to fix the code for you as I'm not convinced that you wrote it in the first place. Right now, your function ends when you find 1 instance of the number you're searching for. Instead of ending execution when you find a value, add that value's index to a list and then return that list when you've completed your search. I'd also suggest removing all the print statements.

EDIT:
Also, for compatibility reasons, I'd change this line middle=(lower+upper)/2 to this middle=(lower+upper)//2

This post has been edited by atraub: 13 August 2012 - 02:25 PM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1