0

I am trying to implement a solution using binary search. I have a list of numbers

list = [1, 2, 3, 4, 6]
value to be searched = 2

I have written something like this

def searchBinary(list, sval):
    low = 0
    high = len(list)

    while low < high:
        mid = low + math.floor((high - low) / 2)

        if list[mid] == sval:
            print("found : ", sval)
        elif l2s[mid] > sval:
            high = mid - 1
        else:
            low = mid + 1

but when I am trying to implement this, I am getting an error like: index out of range. Please help in identifying the issue.

Improve this question
4
  • Why aren't you returning anything? Edit: Nvm, you print it out. Commented Jul 25, 2017 at 18:42
  • What's l2s? Did you mean list there? (Also, never name a variable list... it hides the Python built-in list.) Commented Jul 25, 2017 at 18:46
  • ok, got it. It expects me to return something in case I found the value. Commented Jul 25, 2017 at 18:46
  • You seem to interleav l2s with list... Commented Jul 25, 2017 at 18:46

2 Answers 2

Reset to default
3

A few things.

  1. Your naming is inconsistent. Also, do not use list as a variable name, you're shadowing the global builtin.

  2. The stopping condition is while low <= high. This is important.

  3. You do not break when you find a value. This will result in infinite recursion.

def searchBinary(l2s, sval): # do not use 'list' as a variable
    low = 0
    high = len(l2s) 

    while low <= high: # this is the main issue. As long as low is not greater than high, the while loop must run
        mid = (high + low) // 2

        if l2s[mid] == sval:
            print("found : ", sval)
            return
        elif l2s[mid] > sval:
            high = mid - 1
        else:
            low = mid + 1

And now,

list_ = [1, 2, 3, 4, 6]
searchBinary(list_, 2)

Output:

found :  2
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

UPDATE high = len(lst) - 1 per comments below.

Three issues:

  1. You used l2s instead of list (the actual name of the parameter).
  2. Your while condition should be low <= high, not low < high.
  3. You should presumably return the index when the value is found, or None (or perhaps -1?) if it's not found.

A couple other small changes I made:

  • It's a bad idea to hide the built-in list. I renamed the parameter to lst, which is commonly used in Python in this situation.
  • mid = (low + high) // 2 is a simpler form of finding the midpoint.
  • Python convention is to use snake_case, not camelCase, so I renamed the function.

Fixed code:

def binary_search(lst, sval):
    low = 0
    high = len(lst) - 1

    while low <= high:
        mid = (low + high) // 2

        if lst[mid] == sval:
            return mid
        elif lst[mid] > sval:
            high = mid - 1
        else:
            low = mid + 1

    return None

print(binary_search([1, 2, 3, 4, 6], 2))  # 1
Improve this answer

5 Comments

The issue was because I was initialising high = len(lst), but it should be high = len(lst) - 1. And I read that it is good practice to initialise mid = low + (high-low)/2 to prevent overflow.
You're right that it should be len(lst) - 1. low + (high - low) / 2 is the same as (low + high) / 2. I just simplified the expression.
Yes they are same, but (low + high)/2 can create overflow so that is why it is recommended to use other approach
You're talking about integer overflow if low + high is too large? That seems like a strange concern, and I believe a complete non-issue in Python.
Yes, suppose high=2^31 and low=1, I try to do (high+low) then it will break the code. This is not related to my issue. I just read it while browsing for the solution.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.