#
# searching
#
# Sean Davis, ECS 10, Spring 2014
#

import random
list99 = []

for i in range(1,100) :
  list99 += [i]

list15 = []
for i in range(15) :
  pos = random.randrange(0, len(list99))
#  print pos, list99[pos]
  list15 += [list99[pos]]
  list99 = list99[0:pos] + list99[pos + 1:]

print (list15)

num = eval(input("Please enter a number (-1 = Done): "))
# num = -1
while num != -1 :
  found = False

  for i in range(15):
    if list15[i] == num :
      found = True
      break
    
    
  if found:
    print ("It's there.")
  else :
    print (num, "was not found.")
    
  num =  eval(input("Please enter a number for unsorted (-1 = Done): ")) 

list2 = list15

for i in range(1, len(list2)) :
  temp = list2[i]
  j = i
  while j > 0 and list2[j - 1] > temp :
      list2[j] = list2[j - 1]
      j -= 1

  list2[j] = temp


list15.sort()
print (list15)
print (list2)
num = eval(input("Please enter a number for sorted (-1 = Done): "))

while num != -1 :
  low = 0
  high = len(list15) - 1
  mid = (low + high) // 2

  while low <= high and list15[mid] != num :
    print ("mid =", mid, ", list15[mid] =", list15[mid] )
    if list15[mid] > num :
      high = mid - 1
    else :
      low = mid + 1

    mid = (low + high) // 2

  if low > high :
    print (num, "was not found.")
  else :
    print (num, "is at index position %d." % (mid))

  num = eval(input("Please enter a number for sorted (-1 = Done): "))

  
def search(list15, low, high, num):
  if low > high :
    return -1
  mid = (low + high) // 2
  if list15[mid] == num :
    return mid
  if list15[mid] > num :
    return search(list15, low, mid - 1, num)
  else :
    return search(list15, mid + 1, high, num)

num = eval(input("Please enter a number for search (-1 = Done): "))

while num != -1 :
  print (search(list15, 0, len(list15) - 1, num))
  num = eval(input("Please enter a number for search (-1 = Done): "))