Binary search through strings

Question

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

@FernandoMatsumoto might be a typo. I think he meant middle - 1, middle + 1. — jianweichuah
– jianweichuah, Commented Dec 17, 2015 at 5:35
To do a successful binary search on an array, the data in the array must be in sorted order. The entries for all except Brian are out of position — the sequence should be Brian, Joe, Lois, Meg, Peter, Stewie. — Jonathan Leffler
– Jonathan Leffler, Commented Dec 17, 2015 at 5:35

Bhargav Rao · Accepted Answer · 2017-04-15 14:57:07Z

3

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

edited Apr 15, 2017 at 14:57

Bhargav Rao

52.6k29 gold badges130 silver badges142 bronze badges

answered Dec 17, 2015 at 5:40

jianweichuah

1,4051 gold badge11 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

OneCricketeer Over a year ago

What if you try to find a string tha doesn't exist? What is returned?

jianweichuah Over a year ago

@cricket_007 None. Not sure what the OP's use case is

Yahya Over a year ago

It should be int((start + end) / 2)

Vivek Sable · Accepted Answer · 2015-12-17 08:54:20Z

2

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

edited Dec 17, 2015 at 8:54

Vivek Sable

10.3k6 gold badges45 silver badges63 bronze badges

answered Dec 17, 2015 at 5:44

Prashant Yadav

5512 gold badges10 silver badges26 bronze badges

1 Comment

Fernando Matsumoto Over a year ago

sorted(L) returns a new sorted list with the elements of L. Either use L = sorted(L) or L.sort().

Sunny · Accepted Answer · 2020-10-08 05:50:02Z

0

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

answered Oct 8, 2020 at 5:50

Sunny

1,49515 silver badges20 bronze badges

Collectives™ on Stack Overflow

Binary search through strings

3 Answers 3

3 Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related