# finding more than one item in a list using binary search

Page 1 of 1

## 1 Replies - 1088 Views - Last Post: 13 August 2012 - 09:11 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=288722&amp;s=94d8d2b1de39e11ac9e42dd501ec766e&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 trigger202

Reputation: -1
• Posts: 32
• 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
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

• Pythoneer

Reputation: 827
• Posts: 2,231
• 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