0
\$\begingroup\$

y is the value I am searching for. Is this the correct implementation for binary search?

y= 3
x= range(0,100)
left = 0
right = len(x)-1
mid=int((left+right)/2)

while x[mid]!=y:
    if x[mid]>y:
        right = mid
        mid=int((left+right)/2)
    if x[mid]<y:
        left = mid
        mid=int((left+right)/2)
\$\endgroup\$
  • 1
    \$\begingroup\$ If you're using this code elsewhere and not implementing for the exercise, you should use the bisect module, which has functions which do this for you. \$\endgroup\$ – Bailey Parker Feb 2 '19 at 6:59
4
\$\begingroup\$

PEP-8

PEP-8 is a style guide for Python. It contains several practices which you should follow, like having spaces around operators. Use a tool, like pylint, to ensure you follow these practices.

Integer Division

mid=int((left+right)/2)

Python comes with a built-in integer division operator: //. You should use it.

mid = (left + right) // 2

Termination

while x[mid] != y:

You are searching until you find the desired value. What if the desired value is not present? You will search forever??? Consider adding a different stopping condition.

Redundancy

    if x[mid]>y:
        #...
        mid=int((left+right)/2)
    if x[mid]<y:
        #...
        mid=int((left+right)/2)

Since you are looping while x[mid] != y, your only real choices are for x[mid] > y or x[mid] < y. Instead of testing the second condition, how about using else:?

Since you enter will either the x[mid] > y then clause, or the x[mid] < y then clause, you will always be executing mid=int((left+right)/2). You can safely move those two statements out if the if, and unconditionally execute it at the end. As in:

    if x[mid] > y:
        #...
    else:
        #...
    mid = (left + right) // 2

Efficiency

If you start with left=0, right=99, mid=49, and find x[mid]>y is true, you proceed to search in the range left=0, right=49. But you've already tested x[49] and found the value wasn't there; you don't need to include it in your search range anymore. Similarly, when you find x[mid]<y, you don't need to include that mid point as the left end of your range.

    if x[mid] > y:
        right = mid - 1
    else:
        left = mid + 1

Bug

Your existing algorithm will not terminate for certain numbers. If you search for 99, the value of mid will take on the following values:

49, 74, 86, 92, 95, 97, 98, 98, 98, 98, 98, 98, 98, 98, ...
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.