Python Sorting and Binary Search IndexError: list index out of range

Question

I'm struggling to understand where the error is in this code:

def arr_sort_binsearch(ar):

        ar.sort()

        first = 0
        last = len(ar)-1
        found = False
        item = 8

        for num in ar: 
            while first<=last and not found:
                midpoint = (first + last)//2
                if ar[midpoint] + num == item:
                    found = True
                else:
                    if item < ar[midpoint]:
                        last = midpoint-1
                    else:
                        first = midpoint+1
            print("{} and {} is: {}".format(num, ar[num], item))

ar = [1,3,5,7]
arr_sort_binsearch(ar)

I'm getting an exception that says my index is out of range. I understand the theory of what an index overflow is it's just that I can't find it in my code.

Why are you looping over all elements and also looping to find some value? — Arya McCarthy
– Arya McCarthy, Commented May 11, 2017 at 1:11
To improve your question you should include a fully runnable piece of code that exhibits your issue (by that i mean some code calling your function some appropriate input data) and provide the full traceback error you receive. With these it will be far easier to recognise your issue and suggest a fix. — Paul Rooney
– Paul Rooney, Commented May 11, 2017 at 1:19
Why are you adding num to ar[midpoint]? Wouldn't ar[midpoint] be the value you'd like to test against item? — AetherUnbound
– AetherUnbound, Commented May 11, 2017 at 1:20

snowflake · Accepted Answer · 2017-05-11 01:16:28Z

2

the error is in this statement i think:

print("{} and {} is: {}".format(num, ar[num], item))

num should not be an argument in ar

cheers

answered May 11, 2017 at 1:16

snowflake

9511 gold badge7 silver badges18 bronze badges

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

Comments

Tiny.D · Accepted Answer · 2017-05-11 01:43:33Z

If you try to write a binary search, your code is incorrect.

1, answer your question, why IndexError: list index out of range:

the code for loop over the input list ar as num, and at last print, the element will be the index of ar[num], this raise the error, eg:

you have ar=[1,2,3,4,5,8,9,11,6], when loop to 9, the printtry to use ar[9], but there is only 9 element in the list ar, exceed the maximum index 8, this will raise IndexError: list index out of range.

2, your binary search can be amended like this:

def arr_sort_binsearch(ar,item):

    ar.sort()

    first = 0
    last = len(ar)-1
    found = False

    while first<=last and not found:
        midpoint = (first + last)//2
        if ar[midpoint] == item:
            found = True
        else:
            if item < ar[midpoint]:
                last = midpoint-1
            else:
                first = midpoint+1
    return found

This will return the True or False, if you call function:

arr_sort_binsearch([1,2,3,4,5,8,9,11,6],12) Return False

arr_sort_binsearch([1,2,3,4,5,8,9,11,6],8) Return True

Collectives™ on Stack Overflow

Python Sorting and Binary Search IndexError: list index out of range

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related