3
\$\begingroup\$

This is my version of the binary search method. What more can I do to optimize this?

I have written comments throughout to guide anyone who might find this code helpful through how it operates. But I would like to update it if it can be made faster/cleaner.

def bSearch(arr, val, first, last):

    #Find the index of the middle array value.
    mid = (len(arr)-1)//2

    #If there are no more numbers to search through
    if first >= last:

        #Check if the last number is the number being searched for.
        if (arr[mid] == val):
            print("TRUE")
        else:
            print("FALSE")

    #If there are still numbers to search through
    #check array at index (mid) for the desired value.
    elif (arr[mid] == val):
        print("TRUE")

    elif (arr[mid] < val):
        #nArr = new array = greater half of the original array.
        nArr = arr[len(arr)//2:]
        bSearch(nArr, val, 0, len(nArr)-1)

    elif (arr[mid] > val):
        #nArr = new array = lesser half of the original array.
        nArr = arr[:len(arr)//2]
        bSearch(nArr, val, 0, len(nArr)-1)

#The array used for testing.      
a = [1,2,3,4,6,7,8,10]

print("Test One")
#Search for 5 in array a. Should return false.
bSearch(a, 5, 0, len(a)-1)

print("Test Two")
#Search for 2 in array a. Should return true.
bSearch(a, 2, 0, len(a)-1)

print("Test Three")
#Search for 8 in array a. Should return true.
bSearch(a, 8, 0, len(a)-1)

print("Test Four")
#Search for 1 in array a. Should return true.
bSearch(a, 1, 0, len(a)-1)

print("Test Five")
#Search for 15 in array a. Should return false.
bSearch(a, 15, 0, len(a)-1)
\$\endgroup\$
  • 1
    \$\begingroup\$ Did you try to use timeit to (at least micro-) benchmark this yourself? What problem size do you need to take five seconds? What difference do variations in coding binary search make at that size? How does it compare to bisect? \$\endgroup\$ – greybeard Apr 1 '18 at 4:48
  • \$\begingroup\$ I did not, but these are really helpful tools thank you. \$\endgroup\$ – Allie Marie Apr 1 '18 at 17:31
1
\$\begingroup\$

Non-recursive approach:

# Binary search in a non-empty sorted array
def bin_search(a, val):
    l = 0
    r = len(a)
    # Trying to find val in a[l:r]
    while r - l > 1:
        m = (l + r) // 2
        if a[m] > val:
            r = m
        else:
            l = m
    return a[l] == val
\$\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.