# Spending a target sum, preferably split equally

I have a strange programming prompt. I managed to complete an algorithm to solve smaller test entries (which i'll post). One of my test cases has to complete a 200,000 int input and my algorithm isn't practical. I'll post the prompt and my algorithm. How should I go about optimizing the performance to handle large input sizes?

Prompt:

You and your friend combine your prize tickets at a carnival. You plan to get 2 prizes whose total price is exactly M, M-1, or M-2 tickets (in that order) if possible. M is how many tickets you decide to spend. If there are several prizes that satisfy this condition, you want to minimize the difference between ticket cost.

For example, say you're given M = 5, and prize values of [2,1,4,3].. the output would be 2+3=5.

My SLOW solution:

#sequence actually has +2 values. [0] is how many prizes and [last] is M
#ignore the setting
def checkForPrizes(seq):
M = seq[len(seq)-1] #priori
#    print("M:",M)
n = seq[0] #number of inputs

seq = strip2(seq) #removes the +2 from the "n+2" inputs
quick_sort(seq) #sorts the prize values
#    print("seq:",seq)
returnList = []
leftList = seq[0:int(len(seq)/2)]
rightList = seq[int(len(seq)/2):len(seq)]

current = seq[int(len(seq)/2)]
print("current=",current)

#    print("left half:",leftList)
#    print("right half:",rightList)

s1 = 0 #prize1
s2 = 0 #prize2

flag = False #checks the conditions in order

if (flag is False):
for i in range(len(leftList)):
s1 = leftList[i]
for j in range(len(rightList)):
s2 = rightList[j]
if(s1 + s2 == M):
returnList = [s1,s2]
#                   print("[",s1,",",s2,"] ","is exactly M!",sep="")
flag = True

if(flag is False): #try M-1
for i in range(len(leftList)):
s1 = leftList[i]
for j in range(len(rightList)):
s2 = rightList[j]
if(s1 + s2 == (M-1)):
returnList = [s1,s2]
#                    print("[",s1,",",s2,"] ","is exactly M-1!",sep="")
flag = True

if(flag is False): #try M-2
for i in range(len(leftList)):
s1 = leftList[i]
for j in range(len(rightList)):
s2 = rightList[j]
if(s1 + s2 == (M-2)):
returnList = [s1,s2]
#                    print("[",s1,",",s2,"] ","is exactly M-2!",sep="")
flag = True

if(flag is False):
print("NO")
else:
#        print("sol:",returnList)
dispVal(returnList[0],returnList[1])