Python 3 binary search a sorted variable (list of numbers)

Question

Hello there :) I was writing a program that uses binary search through a sorted list. it should work as follows: python find.py 3 1 2 3

the program should look for 3 in the numbers 1 2 and 3

it should return true and print found needle if it is in 1 2 and 3, if it is not in 1 2 and 3 if should return false and print did not find....

def binary_search(needle, haystack):
    first = 0
    last = len(haystack) - 1
    itemlist = str(input(haystack))
    sorted(itemlist)

    while first <= last:
        mid = (first + last) / 2
        if itemlist[mid] == needle :
            print("Found the needle in the haystack")
            return True
        elif needle < itemlist[mid]:
            last = mid - 1
        else:
            first = mid + 1 
        if not True:
            print("Did not find the needle in the haystack")
            return False

so I tried implementing a standard binary search algorithm, but every version I come across does not take the first number as the item you need to search for in all the following numbers to come... So my question is, how do I set the first variable as the "item" and then everything to come as a list that may or may not contain the item?

I also need to sort that list of x length, so i Tried the sorted function, but since the list can be of any length, i need to sort a variable? I got kinda stuck there.... Any tips on these topics?

Answer 1

sys.argv is a list containing the command line arguments used to invoke the python process. sys.argv[0] is the name of the script and sys.arv[1:] are the remaining arguments. Access it like this:

def binary_search(needle, haystack):
    print('binary_search(): needle = {}, haystack = {}'.format(needle, haystack))
    # your implementation here

if __name__ == '__main__':
    import sys

    if len(sys.argv) > 2:
        needle = sys.argv[1]
        haystack = sys.argv[2:]
        binary_search(needle, haystack)
    else:
        print('Usage: {} needle haystack...'.format(sys.argv[0]))

---

If you need to sort the haystack first, use sorted():

binary_search(needle, sorted(haystack))

However, there is little point in sorting first because that has O(n log n) time complexity, whereas a linear search has only O(n) time complexity. Therefore, if the input is unsorted, it's better to just search by iterating over the list until the target is found.

---

Finally, you might need to convert the input to numeric values in order for the search to work. You can use int() for that:

        needle = int(sys.argv[1])
        haystack = [int(s) for s in sys.argv[2:]]