CODEWITHSUNDEEP
pythonbinary-search
beepboop
beepboop

Reputation: 57

Binary Search Not finding value in List

Not sure what is going on with my code. I have a generic binary search function to return the position in a list. It works half the time.

I have a list with the contents: 

['drag_part_num', 'sku', 'name', 'manufacturer', 'price', 'color', 'diameter', 'finish', 'made in the u.s.a.', 'material', 'model', 'position', 'specific application', 'style', 'type', 'width', 'att_fitment', 'thumbnail', 'small_image', 'image', 'media_gallery', 'type', 'simple_skus']

And this is my binary search:

def binary_search(self, a, x, lo=0, hi=None):   # can't use a to specify default for hi
    hi = hi if hi is not None else len(a) # hi defaults to len(a)   
    pos = bisect_left(a,x,lo,hi)          # find insertion position
    return (pos if pos != hi and a[pos] == x else -1) # don't walk off the end

When i run print self.binary_search(headerList, 'color') It returns -1. I dont see how this is possible.

Thoughts?

Upvotes: 0

Views: 330

Answers (1)

martineau
martineau

Reputation: 123463

For a binary search to work, the list needs to be sorted:

from bisect import bisect_left

def binary_search(a, x, lo=0, hi=None):   # can't use a to specify default for hi
    hi = hi if hi is not None else len(a) # hi defaults to len(a)
    pos = bisect_left(a,x,lo,hi)          # find insertion position
    return (pos if pos != hi and a[pos] == x else -1) # don't walk off the end

header_list = sorted(['drag_part_num', 'sku', 'name', 'manufacturer', 'price',
                      'color', 'diameter', 'finish', 'made in the u.s.a.',
                      'material', 'model', 'position', 'specific application',
                      'style', 'type', 'width', 'att_fitment', 'thumbnail',
                      'small_image', 'image', 'media_gallery', 'type',
                      'simple_skus'])

print(header_list)
print(binary_search(header_list, 'color'))

Output:

['att_fitment', 'color', 'diameter', 'drag_part_num', 'finish', 'image',
 'made in the u.s.a.', 'manufacturer', 'material', 'media_gallery', 'model',
 'name', 'position', 'price', 'simple_skus', 'sku', 'small_image',
 'specific application', 'style', 'thumbnail', 'type', 'type', 'width']
1

Upvotes: 1

Related Questions