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

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

	else:
		middle = (first + last) / 2

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


#---------------------------------------------------
# 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:
#

A = [6, 19, -3, 5, 12, 7, 21, -8, 25, 10, 0, 28, -6, 1, 33, 18, 9, 2, -13, 43]

print
print "Unsorted list is", A
print

A = bubbleSort (A)

print "Sorted list is", A
print

count = [0]

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

found = binarySearch (A, searchVal, 0, (len(A)-1), count)

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

print
print "The number of elements searched in list 'A' was", count[0]
print