<jupyter_start><jupyter_text>Following the online book, [Problem Solving with Algorithms and Data Structures](http://interactivepython.org/runestone/static/pythonds/index.html). Chapter 5 introduces methods for searching and sorting numbers. [Searching](http://interactivepython.org/runestone/static/pythonds/SortSearch/searching.html)We can take advantage of a ordered list by doing a binary search. We start by searching in the middle, if it is not the item that we're searching for, we can use the ordered nature of the list to eliminate half of the remaining items.<jupyter_code>def binary_search(testlist, query):
    if not testlist:
        return False
    else:
        mid_idx = len(testlist) // 2
        mid = testlist[mid_idx]
        if mid == query:
            return True
        elif query < mid:
            return binary_search(testlist[:mid_idx], query)
        else:
            return binary_search(testlist[mid_idx + 1:], query)
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42]
query = 19
print( binary_search(testlist, query) )
query = 3
print( binary_search(testlist, query) )<jupyter_output>True
False<jupyter_text>Keep in mind that this approach requires sorting the list, which may not be ideal if we're simply going to search for 1 number on the very large list (since we have to first sort the list, which is not a cheap operation). HashingImplementing hash table. Source [Hashing](http://interactivepython.org/runestone/static/pythonds/SortSearch/Hashing.html).<jupyter_code>class HashTable:
    """
    a.k.a python's dictionary
    the initial size of the table has been chosen to 
    be 11, although this number is arbitrary, it's important
    for it to be a prime number so that collision resolution 
    will be efficient; this implementation does not handle
    resizing the hashtable when it runs out of the original size
    """
    def __init__(self):
        # slot will hold the key and data will hold the value 
        self.size = 11
        self.slot = [None] * self.size
        self.data = [None] * self.size
    
    def _put(self, key, value):
        hash_value = self._hash(key)
        if self.slot[hash_value] == None:
            self.slot[hash_value] = key
            self.data[hash_value] = value
        elif self.slot[hash_value] == key:
            # replace the original key value
            self.data[hash_value] = value
        else:
            # rehash to get the next location possible
            # if a collision is to occurr
            next_slot = self._rehash(hash_value)
            slot_value = self.slot[next_slot]
            while slot_value != None and slot_value != key:
                next_slot = self._rehash(next_slot)
                slot_value = self.slot[next_slot]

            if self.slot[next_slot] == None:
                self.slot[next_slot] = key
                self.data[next_slot] = value
            else:
                self.data[next_slot] = value
        
    def _get(self, key):
        data = None
        stop = False
        found = False
        start_slot = self._hash(key)
        next_slot  = start_slot      
        while self.slot[next_slot] != None and not found and not stop:
            if self.slot[next_slot] == key:
                data = self.data[next_slot]
                found = True
            else:
                # if we rehash to the starting value
                # then it means the data is not here
                next_slot = self._rehash(next_slot)
                if next_slot == start_slot:
                    stop = True        
        return data
    
    def _hash(self, key):
        return key % self.size
    
    def _rehash(self, oldhash):
        """
        a simple plus 1 rehash, where we add 1 to
        the original value and hash it again to 
        see if the slot it empty (None)
        """
        return (oldhash + 1) % self.size
    
    def __getitem__(self, key):
        # allow access using``[]`` syntax
        return self._get(key)

    def __setitem__(self, key, value):
        self._put(key, value)
H = HashTable()
H[54] = 'cat'
H[26] = 'dog'
H[93] = 'lion'
H[17] = 'tiger'
H[77] = 'bird'
H[44] = 'goat'
H[55] = 'pig'
print(H.slot)
print(H.data)
print(H[55])
print(H[20])<jupyter_output>pig
None<jupyter_text>Sorting[Merge Sort](http://interactivepython.org/runestone/static/pythonds/SortSearch/TheMergeSort.html)<jupyter_code>def merge_sort(alist):
    if len(alist) > 1:
        mid = len(alist) // 2
        left_half = alist[:mid]
        right_half = alist[mid:]
        merge_sort(left_half)
        merge_sort(right_half)
        
        # loop through the left and right half,
        # compare the value and fill them back
        # to the original list
        i, j, k = 0, 0, 0
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                alist[k] = left_half[i]
                i += 1
            else:
                alist[k] = right_half[j]
                j += 1
            k += 1
        
        # after filling in the sorted value,
        # there will be left-over values on
        # either the left or right half, simply
        # append all the left-over values back
        while i < len(left_half):
            alist[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            alist[k] = right_half[j]
            j += 1
            k += 1
            
    return alist
alist = [54, 26, 93, 17, 77]
merge_sort(alist)<jupyter_output><empty_output><jupyter_text>[Quick Sort](http://interactivepython.org/runestone/static/pythonds/SortSearch/TheQuickSort.html)<jupyter_code>def quick_sort(alist):
    _sort(alist, 0, len(alist) - 1)
    
def _sort(alist, first, last):
    if first < last:
        split_point = _partition(alist, first, last)
        _sort(alist, first, split_point - 1)
        _sort(alist, split_point + 1, last)
        
def _partition(alist, first, last):
    right = last
    left = first + 1
    pivot_value = alist[first]
    
    # find the split point of the pivot and move all other
    # items to the appropriate side of the list (i.e. if
    # the item is greater than pivot, then it should be
    # on the right hand side and vice versa)
    done = False
    while not done: 
        while left <= right and alist[left] <= pivot_value:
            left += 1
        while alist[right] >= pivot_value and right >= left:
            right -= 1
        
        if right <= left:
            done = True
        else:
            alist[right], alist[left] = alist[left], alist[right]
    
    # swap pivot value to split point
    alist[first], alist[right] = alist[right], alist[first]
    return right
# list sorted in place
alist = [54, 26, 93, 17, 77, 50]
quick_sort(alist)
alist<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.0930368636629608, 'fraction_numerical': 0.01272674078408426, 'mean_word_length': 2.1477900552486187, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 18, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '178523', 'license': 'MIT', 'n_tokens_mistral': 2171, 'n_tokens_neox': 2050, 'n_words': 668, 'path': 'python/algorithms/search_sort.ipynb', 'repo_name': 'DEVESHTARASIA/machine-learning', 'size': '6836'}