CODEWITHSUNDEEP
pythonbinary-search
soule
soule

Reputation: 21

Binary search through strings

I'm relatively new to python(3.3) and I'm just trying to do a binary search through a list of words, and cant figure out how to fix my operand types when it comes down to looping through the indices... I continue to get the TypeError. Cant figure out any way around it

def find(L, target):
    start = 0
    end = len(L) - 1

    while start <= end: 
        middle = (start + end)// 2 
        midpoint = L[middle]
        if midpoint > target:
            end = midpoint - 1
        elif midpoint < target:
            start = midpoint + 1
        else:
            return midpoint

I'm calling the function as so:

L = ["Brian", "Meg", "Peter", "Joe", "Stewie", "Lois"]

find(L, "Joe")

Upvotes: 2

Views: 21213

Answers (3)

Sunny
Sunny

Reputation: 1456

def binarySearchOnString(arr, x):
        l = 0
        r = len(arr) - 1
        while (l <= r): 
            m = (l + r) // 2 
            if (arr[m] == x): 
                return m
            elif (arr[m] < x): 
                l = m + 1
            else: 
                r = m - 1
        return -1  #   If element is not found  then it will return -1

Upvotes: 0

jianweichuah
jianweichuah

Reputation: 1427

Your logic seems fine, except for the input and the bug with incrementing and decrementing midpoint instead of middle.

def find(L, target):
    start = 0
    end = len(L) - 1

    while start <= end:
        middle = (start + end)/ 2
        midpoint = L[middle]
        if midpoint > target:
            end = middle - 1
        elif midpoint < target:
            start = middle + 1
        else:
            return midpoint

L = ["Brian", "Joe", "Lois", "Meg", "Peter", "Stewie"] # Needs to be sorted.

print find(L, "Peter")

Upvotes: 3

Prashant Yadav
Prashant Yadav

Reputation: 551

def find(L, target):
    start = 0
    end = len(L) - 1
    while start <= end:
        middle = (start + end)// 2
        midpoint = L[middle]
        if midpoint > target:
            end = middle - 1
        elif midpoint < target:
            start = middle + 1
        else:
            return midpoint

    L = ["Brian", "Joe", "Lois", "Meg", "Peter", "Stewie"]
    L = sorted(L)
    print(find(L, "Lois"))

As pointed out by others, use middle instead of midpoint

And to optimally use binary search, sort the list first

Upvotes: 2

Related Questions