#---------------------------------------------------
# Function name:  sortedSearch
#   Input:   list -> the list of sorted elements
#            searchItem -> the search value
#   Output:  the index where the search value was found in the list,
#                or -1, if the search value is not found

def sortedSearch (list, searchItem):
	index = 0
	while (index < len(list)):
		if (list[index] == searchItem):
			return index
		else:
			if (list[index] > searchItem):
				return -1
		index = index + 1

	return -1


#---------------------------------------------------
# Function name:  bubbleSort
#   Input:      an unsorted list
#   Output:     the sorted list

def bubbleSort (list):
	n = len(list)		# number of elements in list
	passNum = 1		# start with the 1st pass
	swap = 1		# initialize 'swap' to 1 to start 1st pass

	while ((passNum < n) and (swap == 1)):
		index = 0
		swap = 0

		while (index < (n-passNum)):
			if (list[index] > list[index+1]):
				temp = list[index+1]
				list[index+1] = list[index]
				list[index] = temp
				swap = 1
			index = index + 1

		passNum = passNum + 1

	return list


#---------------------------------------------------
# Main program:
#

names = ["Sue", "Mark", "William", "Cora", "Beth", "Tyler", "Ann", "June", "David"]
# names = ["Steve", "Garrett", "Danyu", "Krystal", "Chau", "Winnie", "Peter"]


print
print "Unsorted list is", names
print

names = bubbleSort (names)

print "Sorted list is", names
print

searchVal = raw_input("What name do you want to search for? ")
print

found = sortedSearch (names, searchVal)

if (found != -1):
	print "The search string was found in list 'names' at index", found
else:
	print "The search string was not found in list 'names'"

print