CODEWITHSUNDEEP
python
Bellfrank
Bellfrank

Reputation: 33

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

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)

Upvotes: 0

Views: 53

Answers (4)

Red
Red

Reputation: 27557

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)

Upvotes: 0

Iyanu Adelekan
Iyanu Adelekan

Reputation: 406

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?.

Upvotes: 0

Jiř&#237; Baum
Jiř&#237; Baum

Reputation: 6930

  • 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.

Upvotes: 1

Sam
Sam

Reputation: 1415

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.

Upvotes: 0

Related Questions