<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
顺序查找
无序查找
时间复杂度 O(n)。
有序查找
时间复杂度 O(n)，平均时间复杂度 n/2。
二分查找
二分查找适用于有序列表的查找。复杂度 O(logn)。
Step1:  hash 查找
Sorting
冒泡排序
时间复杂度最高的排序，存在许多冗余的交换。但是由于其比较了所有元素，可以识别已排序的列表。
a bubble sort may have an advantage in that it will recognize the sorted list and stop.
Step2:  选择排序
Step3:  插入排序
Step4:  The Shell Sort
与插入排序类似，但是是先将列表分割成子列表后进行插入排序，最后把排序后的子列表再进行排序。
Merge Sort 归并排序
典型的分治法。
<ASSISTANT_TASK:>
Python Code:
def binary_search(list_, item):
    if len(list_) == 0:
        return False
    middle = len(list_) / 2
    if item == list_[middle]:
        return True
    else:
        if item > list_[middle]:
            return binary_search(list_[middle+1:], item)
        else:
            return binary_search(list_[:middle-1], item)
print binary_search([0, 1, 2, 8, 13, 17, 19, 32, 42], 32)
    
Explanation: Searching and Sorting
Searching
顺序查找
无序查找
时间复杂度 O(n)。
有序查找
时间复杂度 O(n)，平均时间复杂度 n/2。
二分查找
二分查找适用于有序列表的查找。复杂度 O(logn)。
End of explanation
def bubble_sort(list_):
    for passnum in range(len(alist)-1,0,-1):
        for i in range(passnum):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]
alist = [54,26,93,17,77,31,44,55,20]
bubble_sort(alist)
print(alist)
Explanation: hash 查找
Sorting
冒泡排序
时间复杂度最高的排序，存在许多冗余的交换。但是由于其比较了所有元素，可以识别已排序的列表。
a bubble sort may have an advantage in that it will recognize the sorted list and stop.
End of explanation
def selection_sort(alist):
    for fillslot in range(len(alist)-1,0,-1):
        positionOfMax=0
        for location in range(1,fillslot+1):
            if alist[location]>alist[positionOfMax]:
                positionOfMax = location
        temp = alist[fillslot]
        alist[fillslot] = alist[positionOfMax]
        alist[positionOfMax] = temp
alist = [54,26,93,17,77,31,44,55,20]
selection_sort(alist)
print(alist)
Explanation: 选择排序
End of explanation
def insertion_sort(alist):
    for index in range(1,len(alist)):
        currentvalue = alist[index]
        position = index
        while position>0 and alist[position-1]>currentvalue:
            alist[position]=alist[position-1]
            position = position-1
        alist[position]=currentvalue
alist = [54,26,93,17,77,31,44,55,20]
insertion_sort(alist)
print(alist)
Explanation: 插入排序
End of explanation
def merge_sort(alist):
    if len(alist) <= 1:
        return alist
    print "Split", alist
    mid = len(alist) / 2
#     递归调用
    left = merge_sort(alist[:mid])
    right = merge_sort(alist[mid:])
    return merge(left, right)
def merge(left_half, right_half):
    i = j = 0
    result = []
    while i < len(left_half) and j < len(right_half):
        if left_half[i] < right_half[j]:
            result.append(left_half[i])
            i += 1
        else:
            result.append(right_half[j])
            j += 1
    result += left_half[i:]
    result += right_half[j:]
    print "Merge", result
    return result
alist = [54,26,93,17,77,31,44,55,20]
result = merge_sort(alist)
print(result)
Explanation: The Shell Sort
与插入排序类似，但是是先将列表分割成子列表后进行插入排序，最后把排序后的子列表再进行排序。
Merge Sort 归并排序
典型的分治法。
End of explanation
<END_TASK>