CODEWITHSUNDEEP
pythonbinary-search
user11004300
user11004300

Reputation:

I wanted to do a Binary search but the result is faulty

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))

Upvotes: 1

Views: 140

Answers (3)

Ishan Arora
Ishan Arora

Reputation: 124

Please go through this:

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 newl[check] > a:              #fixed the bug here
        for x in newl[:check]:
            if x == a:
                return True

    if newl[check] < a:             #fixed the bug here
        for x in newl[check:]:
            if x == a:
                return True

    return False        #Return false should be universal. When the entire search fails it should be called.

print(clist(7))

Upvotes: 1

ComplicatedPhenomenon
ComplicatedPhenomenon

Reputation: 4189

Your function is not binary search, you are checking element by element of a sorted list after checking the middle element.

def binary_search(arr, i):
    n = len(arr)
    arr = sorted(arr)
    left = 0
    right = n - 1

    # Define the condition when the loop should be broken 
    while (left <= right):
        mid = left + (right-left) // 2
        if arr[mid] == i:
            return True
        elif arr[mid] < i:
            left = mid + 1 
        else:
            right = mid - 1
    return False

l = [2,6,5,9,7,1,4,8,3]
i = 7
binary_search(l, i)

Upvotes: 0

Hitmands
Hitmands

Reputation: 14179

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

Upvotes: 2

Related Questions