Linear searching looks through a list/array item by item until a target value is found, or the end of the list is reached. Linear searches can use unsorted lists, but are very inefficient.

Binary searches only work on sorted lists, with the list repeatedly split into smaller and smaller lists, until the target value is found or the list is empty.

Pointers are used to identify the range of the list to be sorted (low/high, bottom/top, left/right, start/end). An index is chosen between the two pointers, resulting in a match or a value that is too high/low. In the latter case the range pointers are updated, excluding the index that has just been checked.

General Algorithm

bottom = 0
top = listsize - 1
found = False
 
loop while bottom<=top and found = False do
    middle = int( (top+bottom)/2 )      #pick a midpoint
    if list[middle] = target then
        found = True                    #item found
    else if list[middle] > target then
        top = middle - 1                #look in bottom half
    else
        bottom = middle + 1             #look in top half
    end if
end loop
 
if found = True then 
    print "Found at index: " + middle
else
    print "Not found"
end if

#set pointers to start and end of full list
start = 0
end = len(array)
found = False

# as long as pointers haven't crossed, and target has not been found
while (start <= end) and not found:
 
    # pick the midpoint between pointers
    middle = (start + end) // 2
 
    # has target been found?
    if target == array[middle]:
        found = True
    # is target in lower half of range (start-middle)?
    elif target < array[middle]:
        end = middle - 1
    # target must be in upper half (middle-end)
    else:
        start = middle + 1
 
# item has or has not been found 
if found:
    print "Found at index" , middle
else:
    print "Not found"

Python functions terminate as soon as a value is returned. This can remove the need for a “found” variable:

def binary_search(array, target):
    start = 0
    end = len(array)

    while start <= end:
        middle = (start + end) // 2
        if target == array[middle]:
            return middle

        if target < array[middle]:
            end = middle - 1
        else:
            start = middle + 1

    return -1