Introduction

Binary Search is an efficient algorithm used to find the position of a target value within a sorted array or list.
The algorithm works by repeatedly dividing the search interval in half. If the value of the target is less than the value in the middle, the search continues in the lower half, otherwise, it continues in the upper half.
This technique significantly reduces the time complexity, making it much faster than linear search for large datasets.

Objective

The objective of this tutorial is to demonstrate how to implement the Binary Search algorithm in Python. By the end of this tutorial, you will understand how to apply binary search to sorted lists and find the position of a target element efficiently.

Python Code for Binary Search

def binary_search(arr, target):
    """
    Function to perform binary search on a sorted list.
    :param arr: Sorted list of elements.
    :param target: The element to be searched in the list.
    :return: The index of the target if found, otherwise -1.
    """
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
            
    return -1

# Example usage:
arr = [1, 3, 5, 7, 9, 11, 13, 15]
target = 7
result = binary_search(arr, target)

if result != -1:
    print(f"Element {target} found at index {result}.")
else:
    print(f"Element {target} not found in the array.")
        

Program Explanation

The provided Python program implements the Binary Search algorithm. Let’s break down its structure:

• Function Definition:
  The function binary_search(arr, target) takes two arguments: a sorted array arr and the target value that needs to be found.
• Initializing Variables:
  The variables low and high represent the start and end indices of the list, respectively.
• While Loop:
  The loop continues as long as low is less than or equal to high. In each iteration, it calculates the middle index mid.
• Conditional Checks:
  – If the value at arr[mid] is equal to the target, it returns the index mid.
  – If arr[mid] is less than the target, it means the target lies in the right half of the array, so low is updated to mid + 1.
  – If arr[mid] is greater than the target, the search continues in the left half by updating high to mid - 1.
• Return Value:
  If the target element is not found after the loop terminates, the function returns -1 indicating that the target is absent in the array.

How to Run the Program:

1. Open your preferred Python environment or IDE (such as VSCode, PyCharm, or Jupyter Notebook).
2. Copy the provided Python code and paste it into a Python file, e.g., binary_search.py.
3. Execute the script by running the command python binary_search.py.
4. The program will search for the specified target value in the array and print the result to the console.