Python: Binary Search on List

1. Introduction

Binary Search is a searching algorithm that finds the position of a target value within a sorted list or array. It compares the target value to the middle element of the list; if they are unequal, the half in which the target cannot lie is eliminated, and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not on the list. 

The key idea behind Binary Search is that it reduces the problem size by half with each step, making it much more efficient than linear search for large lists.

2. Program Overview

In this program, we will:

1. Define a function binary_search which takes a sorted list and a target value as parameters.

2. Implement the logic to repeatedly divide the list in half until the target is found or the list is exhausted.

3. Return the index of the target value if found, else return -1.

3. Code Program

def binary_search(arr, x):
    """Perform binary search to find the index of x in arr."""
    # Defining the initial left and right pointers.
    l = 0
    r = len(arr) - 1

    while l <= r:
        mid = (l + r) // 2

        # If element is present at the middle.
        if arr[mid] == x:
            return mid

        # If element is smaller, it can only be present in the left sub-array.
        elif arr[mid] < x:
            l = mid + 1

        # Else, the element is in the right sub-array.
        else:
            r = mid - 1

    # Element is not present in the list.
    return -1


# Demonstration
arr = [1, 3, 5, 7, 9, 11, 13, 15]
x = 9

result = binary_search(arr, x)
if result != -1:
    print(f"Element {x} is present at index {result}")
else:
    print(f"Element {x} is not present in the list")

Output:

Element 9 is present at index 4

4. Step By Step Explanation

1. We first define our function binary_search which will take a sorted list arr and an element x which we wish to search for.

2. We set our pointers l and r to the start and end of the list respectively.

3. In each iteration of the while loop, we calculate the mid index of the current segment of the list.

4. If the middle element is the target, we return its index.

5. If the middle element is less than the target, it means our target lies to the right of mid, so we update l to mid + 1.

6. If the middle element is greater than the target, our target lies to the left of mid, so we update r to mid-1.

7. If our loop completes without returning, it means the target isn't in the list, so we return -1.