<jupyter_start><jupyter_text>It is a study note over http://interactivepython.org/runestone/static/pythonds/index.html by <NAME>, <NAME>  which is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.  Searching Shared and adapted by: YinTaiChen In Python, there is a very easy way to ask whether an item is in a list of items. We use the __in__ operator.<jupyter_code>15 in [3, 5, 2, 4, 1]
3 in [3, 5, 2, 4, 1]<jupyter_output><empty_output><jupyter_text>The Sequential Search Starting from the first item in the list, we simply move from item to item, following the underlying sequential order until we either find what we are looking for or run out of items.<jupyter_code>def sequentialSearch(alist, item):
    pos = 0
    found = False
    
    while pos < len(alist) and not found:
        if alist[pos] == item:
            found = True
        else:
            pos = pos+1
    
    return found
testlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]
print(sequentialSearch(testlist, 3))
print(sequentialSearch(testlist, 13))<jupyter_output>True<jupyter_text>Analysis of Sequential Search | __Case__ | __Best Case__ | __Worst Case__ | __Average Case__ ||----------|---------------|----------------|------------------|| item is present | 1 | n | n/2 || item is not present | n | n | n |  What if the list is ordered? In some cases, the algorithm does not have to continue looking through all of the items to report that the item was not found.<jupyter_code>def orderedSequentialSearch(alist, item):
    pos = 0
    found = False
    stop = False
    while pos < len(alist) and not found and not stop:
        if alist[pos] == item:
            found = True
        else:
            if alist[pos] > item:
                stop = True
            else:
                pos = pos+1
                
    return found
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42]
print(orderedSequentialSearch(testlist, 3))
print(orderedSequentialSearch(testlist, 13))<jupyter_output>True<jupyter_text>The Binary Search Instead of searching the list in sequence, a __binary search__ will start by examing the middle term. If it is not the correct item, we can use the ordered nature of the list to eliminate half of the remaining items.<jupyter_code>def binarySearch(alist, item):
    first = 0
    last = len(alist)-1
    found = False
    
    while first<=last and not found:
        midpoint = (first + last) // 2
        if alist[midpoint] == item:
            found = True
        else:
            if item < alist[midpoint]:
                last = midpoint-1
            else:
                first = midpoint+1
                
    return found
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42]
print(binarySearch(testlist, 3))
print(binarySearch(testlist, 13))<jupyter_output>True<jupyter_text>This algorithm is a great example of a divide and conquer strategy.  Recursive Version of Binary Search<jupyter_code>def r_binarySearch(alist, item):
    if len(alist) == 0:
        return False
    else:
        midpoint = len(alist) // 2
        if alist[midpoint]==item:
            return True
        else:
            if item < alist[midpoint]:
                return r_binarySearch(alist[:midpoint], item)
            else:
                return r_binarySearch(alist[:midpoint], item)
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42]
print(r_binarySearch(testlist, 3))
print(r_binarySearch(testlist, 13))<jupyter_output>True
StarcoderdataJupyterStructuredCleanDedup