My code works but I don't think I'm using the right method

Question

Summary: Function searches an array for a number, and if found it will return found, etc. The code works, it gives me the right response, but is this the proper way to set up an array, or is it searching a list? I am new to programming and I believe that an array is better (faster) not sure why tho?

array = [2, 3, 5, 7, 11, 13, 17, 19, 
23, 29, 31, 37, 41, 43, 
    47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

targetValue = int(input())


def binarySearch(array, targetValue):
    min = 0
    max = len(array) - 1
    found = 'Number is not in array'

    while (min <= max):
        middle = (min + max)/2

        if array[middle] == targetValue:
            found = 'We found the number in the array!'
            return found

        else:
            if targetValue < array[middle]:
                max = middle - 1
            else: 
                min = middle + 1
    return found


index = binarySearch(array, targetValue)
print (index)

This isn't directly related to your question, but a purely algorithmic function like `binarySearch()` should not return cute messages. Rather, it should return fundamental values appropriate to the problem at hand: for example, `True` vs `False` or the number found vs `None`. If your program needs to print a message based on the outcome, deal with those messages outside the `binarySearch()` function, not inside. Also, don't forget that Python has `elif`, which would let you flatten the conditional code by one level. — FMc, Jun 15 '20 at 00:17
Questions asking "how do I improve this already working code" are better suited to [codereview.se] — pppery, Jun 15 '20 at 00:52

score 1 · Answer 1 · answered Jun 15 '20 at 00:17

The code itself looks good; the main feedback would be that (in Python 3) the / operator will give floating-point numbers (eg. 5 / 2 gives 2.5). You probably want the // operator, which gives the whole number (eg. 5 // 2 gives 2).
If you're using this in a real project (rather than as an exercise), the standard library has a bisect module, which does exactly this.
As for why it's faster, think how many times it has to go through the loop; each time through it eliminates half the array; with 25 elements, it only has to go through a maximum of ~5 times (log₂ 25). More importantly, it will scale nicely — doubling the size of the array only adds one extra loop, increasing it by 10× only adds an extra 3–4 loops, increasing it by 1000× only adds 10 loops.

Red · Answer 2 · 2020-06-15T00:29:28.390

Here's a simplified version:

array = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
targetValue = int(input())

def binarySearch(array, targetValue):
    min = 0
    max = len(array) - 1
    while True:
        middle = (min + max)//2
        if array[middle] == targetValue:
            return 'We found the number in the array!'
        if targetValue < array[middle]:
            max = middle - 1
        else: 
            min = middle + 1

index = binarySearch(array, targetValue)
print (index)

score 0 · Answer 3 · answered Jun 15 '20 at 00:12

This looks mostly correct. One issue is that here:

middle = (min + max)/2
if array[middle] == targetValue:

middle might not be an integer, it might be a float after the division. So you need to wrap it in an int call:
middle = int((min+max)/2.0)

I assume this is a coding exercise, there are much "easier" ways to accomplish this, such as: if targetValue in array - note that your variable array is a python list, not an array object.

score 0 · Answer 4 · answered Jun 15 '20 at 00:22

It seems you implemented your binary search algorithm in Python, so to answer your question, yes, you defined an array properly. In python a 'list' is effectively a dynamic array.

Python however does have a native array type. You can check this thread to find out more about the topic Python List vs. Array - when to use?.

My code works but I don't think I'm using the right method

4 Answers4