Binary Search Algorithm

Want to learn more? Check out Data Structures and Algorithms in Python

Create Sorted List

We need a sorted list for binary search algorithm. This can be created using these two lines:

1
2
3
sorted_list = list(range(20))

sorted_list

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

Create A Binary Search Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# Define a function that takes a sorted list and the value we want to find,
def binary_search(sorted_list, target):

    # Set the initial search area to be the whole list
    search_area = sorted_list

    # While the search area has at least 1 element,
    while len(search_area) >= 1:

        # Print the current search area:
        print('Search area:', search_area)

        # Create the index of the last element
        end = len(search_area) - 1

        # Create the index of the first element
        middle = int((0 + end)/2)

        # If target is smaller than the middle value of the search area
        if target < search_area[middle]:
            # Make the new search area the first half of the current search area
            search_area = search_area[:middle]

        # If target is greater than the middle value of the search area
        elif target > search_area[middle]:
            # Make the new search area the second half of the current search area
            search_area = search_area[middle:]

        # If the target is equal to the middle value of the search area:
        else:
            # Print success!
            return print('Found it!', str(search_area[middle]))
    # If the list area has 0 elements, print that search failed
    else:
        return print('Not in list!')

# Run function
binary_search(sorted_list, 7)

Search area: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
Search area: [0, 1, 2, 3, 4, 5, 6, 7, 8]
Search area: [4, 5, 6, 7, 8]
Search area: [6, 7, 8]
Found it! 7