Ad

I Wanted To Do A Binary Search But The Result Is Faulty

- 1 answer

I wanted to do binary search on a list but the result shows 'false' even if I check a number from the list.

def clist(a):

    l = [2,6,5,9,7,1,4,8,3]
    newl = sorted(l)
    check = int(1+len(newl)/2)

    if newl[check] == a:
        return True

    if check > a:
        for x in newl[:check]:
            if x == a:
                return True
            return False

    if check < a:
        for x in newl[check::]:
            if x == a:
                return True
            return False

print(clist(7))
Ad

Answer

You could write your script in such a way that:

  1. take the element at the middle of the list
  2. return it if that's what you need
  3. if your needle is gt than the middle, then call bsearch on the remaining right side of the list
  4. othwewise call bsearch with the left side
def bsearch(needle, haystack):
    l = len(haystack)
    half = int(l / 2)
    element = haystack[half];

    if element == needle:
        return element

    if needle <= element:
        return bsearch(needle, haystack[0:half])

    if needle > element:
        return bsearch(needle, haystack[half:l])




print(bsearch(7, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]))

in binary search:

  1. list must be ordered
  2. as stated by @tripleee, you have to recursively split the list in halves
Ad
source: stackoverflow.com
Ad