#---------------------------------------------------
# Function name:  binarySearch
#   Input:   list -> the array of sorted elements
#            searchItem -> the search value
#            first -> the index of the first element in the
#                 section of array list to search
#            last -> the index of the last element in the
#                 section of array list to search
#   Output:  the index where the search value was found in the array,
#                or -1, if the search value is not found

def binarySearch (list, searchItem, first, last):
	if (first > last):
		return -1

	else:
		middle = (first + last) / 2

		if (list[middle] == searchItem):
			return middle
		else:
			if (list[middle] > searchItem):
				return binarySearch (list, searchItem, first, middle-1)
			else:
				return binarySearch (list, searchItem, middle+1, last)


#---------------------------------------------------
# Function name:  bubbleSort
#   Input:      an array, list
#   Output:     the sorted array, 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 names
print

names = bubbleSort (names)

print names
print

found = binarySearch (names, "Sue", 0, (len(names)-1))

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