<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Searching and Sorting
Searching
Process of selecting information from a collection based on specific criteria. 
Linear Search
Simplest approach to searching problem is sequential or linear search. It's basically starting from first element and goint one by one untill the item found. 
In Python, a specific item can be found with in operator
Step1:  Okay, using in operator gives us a great deal of simplicity, but we should know the behind the scenes of in operator.
Step2:  Finding a specific item from unsorted list resulted worst case time of O(n), since it has to go all the way to the end n iteration.
What about if we search through Sorted sequence? Since we know that the list is sorted we might avoid going through the end, we can terminate it if we came to bigger number than our target. This produces the somewhat better version than the unsorted linear search but complexity is still the same.
Step3:  Finding the Smallest Value
It is equivalen to min() function in Python. To be able to accomplish this we have to do linear search but this time we have to keep track of the smallest number. Complexity is O(n) again.
Step4:  We can do the same thing for finding the maximum number, Python's max() implementation
Step5:  The Binary Search
Step6:  Sorting
Sorting is the process of ordering or arranging a collection of items.
Bubble Sort
Step7:  Selection Sort
Step8:  Insertion Sort
Step9:  Working ith Sorted Lists
We can increase the efficiency of some algorithms by making input list a sorted list. 
Maintaining a Sorted List
To maintain a sorted list new items must be inserted into their proper position. Instead of using append() method we have to locate proper position and use insert() method.
<ASSISTANT_TASK:>
Python Code:
theArray = range(0,100)
key = 101
if key in theArray:
    print("The key is in the array.")
else:
    print("The key is not in the array.")
Explanation: Searching and Sorting
Searching
Process of selecting information from a collection based on specific criteria. 
Linear Search
Simplest approach to searching problem is sequential or linear search. It's basically starting from first element and goint one by one untill the item found. 
In Python, a specific item can be found with in operator
End of explanation
def linearSearch(theValues, target):
    n = len(theValues)
    for i in range(n):
        # If the target is in the ith element, return True
        if theValues[i] == target:
            return True
    # If not found, return False.
    return False
        
Explanation: Okay, using in operator gives us a great deal of simplicity, but we should know the behind the scenes of in operator.
End of explanation
def sortedLinearSearch(theValues, item):
    n = len(theValues)
    for i in range(n):
        # If the target is found in the ith element, return True
        if theValues[i] == item:
            return True
        # If target is largers than the ith element, it's not in the sequence.
        elif theValues[i] > item:
            return False
    
    # The item is not in the sequence.
    return False
Explanation: Finding a specific item from unsorted list resulted worst case time of O(n), since it has to go all the way to the end n iteration.
What about if we search through Sorted sequence? Since we know that the list is sorted we might avoid going through the end, we can terminate it if we came to bigger number than our target. This produces the somewhat better version than the unsorted linear search but complexity is still the same.
End of explanation
def findSmallest(theValues):
    n = len(theValues)
    # Assume the first item is the smallest value
    smallest = theValues[0]
    # Determine if any other item in the sequence is smaller.
    for i in range(1,n):
        if theValues[i] < smallest:
            smallest = theValues[i]
    # Return the smallest found.
    return smallest
Explanation: Finding the Smallest Value
It is equivalen to min() function in Python. To be able to accomplish this we have to do linear search but this time we have to keep track of the smallest number. Complexity is O(n) again.
End of explanation
def findBiggest(theValues):
    n = len(theValues)
    # Assuming the first item is the biggest value
    biggest = theValues[0]
    # Determine if any other item in the sequence is bigger.
    for i in range(1, n):
        if theValues[i] > biggest:
            biggest = theValues[i]
    #Return the biggest found.
    return biggest
Explanation: We can do the same thing for finding the maximum number, Python's max() implementation
End of explanation
def binarySearch(theValues, target):
    # Start with the entire sequence of elements. 0:length
    low = 0 
    high = len(theValues - 1)
    
    # Repeatedly subdivide the sequence in half until the target is found.
    while low <= high:
        # Find the midpoint of the sequence.
        mid = (high + low) // 2
        # Does the midpoint contain the target?
        if theValues[mid] == target:
            return True
        # Or does the target precede the midpoint?
        elif target < theValues[mid]:
            high = mid - 1 # Update the upper bound
            
        # Or does it follow the midpoint
        else:
            low = mid + 1 # Update the lower bound
            
    # If the sequence cannot be subdivided further, we're done.
    return False
Explanation: The Binary Search
End of explanation
# Sorts a sequence in ascending order using the bubble sort algorith.
def bubbleSort(seq):
    not_sorted = True
    n = len(seq)
    print "At the beginning: "
    print seq
    while not_sorted:
        # If following statements fail next statement will stop the loop
        not_sorted = False
        for i in range(n-1):
            if seq[i] <= seq[i+1]:
                continue;
            else:
                temp = seq[i]
                seq[i] = seq[i+1]
                seq[i+1] = temp
            not_sorted = True
            print seq
    return seq
import random
_list = random.sample(xrange(1, 101), 10)
_list
bubbleSort(_list)
Explanation: Sorting
Sorting is the process of ordering or arranging a collection of items.
Bubble Sort
End of explanation
# Sorts a sequence in ascending order using the selection sort algorithm
def selectionSort(theSeq):
    n = len(theSeq)
    for i in range(n-1):
        # Assume the ith element is the smallest.
        smallNdx = i
        for j in range(i+1, n):
            if theSeq[j] < theSeq[smallNdx]:
                smallNdx = j
        
        # Swap the ith value and smallNdx value only if the smallest value is 
        # not really in its proper position. Some implementations omit testing 
        # the condition and always swap the two values.
        if smallNdx != i:
            tmp = theSeq[i]
            theSeq[i] = theSeq[smallNdx]
            theSeq[smallNdx] = tmp
    return theSeq
import random
_list = random.sample(xrange(1, 101), 10)
print _list
selectionSort(_list)
Explanation: Selection Sort
End of explanation
# Sorts a sequence in ascending order using the insertion sort algorithm.
def insertionSort(theSeq):
    n = len(theSeq)
    # Starts with the first item as the only sorted entry.
    for i in range(1, n):
        # Save the value to be positioned.
        value = theSeq[i]
        # Find the position where value fits in the ordered part of the list.
        pos = i
        while pos > 0 and value < theSeq[pos - 1]:
            # Shift the items to the rigth during search
            theSeq[pos] = theSeq[pos - 1]
            pos -= 1
            
        theSeq[pos] = value
    return theSeq
import random
_list = random.sample(xrange(1, 101), 10)
_list
insertionSort(_list)
Explanation: Insertion Sort
End of explanation
# Modified version of the binary search that returns the index within 
# a sorted sequence indicating where the target should be located.
def findSortedPosition(theList, target):
    low = 0 
    high = len(theList) - 1
    while low <= high:
        mid = (high + low) // 2
        if theList[mid] == target:
            # Index of the target
            return mid
        elif target < theList[mid]:
            high = mid - 1
        else:
            low = mid + 1
            
    # Index where the target value should be.
    return low
_list = range(1,24,2)
print(_list)
print("Index is ", findSortedPosition(_list, 12))
Explanation: Working ith Sorted Lists
We can increase the efficiency of some algorithms by making input list a sorted list. 
Maintaining a Sorted List
To maintain a sorted list new items must be inserted into their proper position. Instead of using append() method we have to locate proper position and use insert() method.
End of explanation
<END_TASK>