Binary Search in python made easy

Think of the binary search algorithm as searching for a specific book in a library. You start in the middle of the shelves and determine if the book you’re looking for is on the left or right side of the shelves. Then you move to that side of the shelves and repeat the process until you find the book or determine that it’s not in the library.

Here’s an implementation of the binary search algorithm in Python:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Explanation of each line:

1. The binary_search function takes two arguments, arr and target. arr is the list of values to search through, and target is the value you're looking for.
2. left, right = 0, len(arr) - 1 sets left to 0 and right to the index of the last element in arr. These are the boundaries of the search.
3. while left <= right is the condition that allows us to keep searching as long as there are still elements to look at.
4. mid = (left + right) // 2 calculates the index of the middle element in the current section of the list.
5. if arr[mid] == target checks if the value at the mid index is equal to the target. If it is, the function returns mid because we've found the target.
6. elif arr[mid] < target checks if the value at the mid index is less than the target. If it is, the search continues in the right half of the list, so left is set to mid + 1.
7. else is executed if the value at the mid index is greater than the target. The search continues in the left half of the list, so right is set to mid - 1.
8. If the loop exits, it means the target wasn’t found, so the function returns -1.

Limitations:

1. The binary search algorithm only works if the list is sorted. If the list is not sorted, the algorithm won’t return the correct result.
2. The binary search algorithm is less efficient than other search algorithms when searching through large lists. For very large lists, it may be faster to use a different search algorithm.
3. The binary search algorithm can only be used to search for a value in a list, not to find the index of the first occurrence of a value.

When to use:

1. Use the binary search algorithm when searching through a large, sorted list.
2. Use the binary search algorithm when searching for a specific value in a list, not the first occurrence of a value.
3. Use the binary search algorithm when the list is too large to search through linearly.