lesson1Title

lesson2Title

lesson3Title

lesson4Title

lesson5Title

lesson6Title

pythonIntroAlgorithms1Chapter3Title

lesson7Title

lesson8Title

lesson9Title

lesson10Title

lesson11Title

lesson12Title

lesson13Title

lesson14Title

lesson15Title

lesson16Title

lesson17Title

lesson18Title

lesson19Title

pythonIntroAlgorithms1Chapter1Title

pythonIntroAlgorithms1Chapter2Title

pythonIntroAlgorithms1Chapter4Title

def binary_search(arr, target):
    start, end = 0, len(arr) - 1

    while start <= end:
        mid = (start + end) // 2

        if arr[mid] == target: # If found, return the middle index
            return mid
        elif arr[mid] < target: # If target is greater than the mid value, check the right side
            start = mid + 1
        else: # If target is less than the mid value, check the left side
            end = mid - 1

    return -1  # If not found


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

target = 7

result = binary_search(arr, target)

print(result)

# In-Depth Look at Binary Search

## 1. Initial Range Setup

Set up the start and end points of the search range.

```python title="Initial Range Setup"
def binary_search(arr, target):
    start, end = 0, len(arr) - 1
```

<br />

## 2. Iterative Comparison and Range Adjustment

Check the middle element and halve the search range.

```python title="Iterative Comparison and Range Adjustment"
while start <= end:
    mid = (start + end) // 2  # midpoint
    if arr[mid] == target:  # found the target
        return mid
    elif arr[mid] < target:  # target is larger than the midpoint value
        start = mid + 1
    else:  # target is smaller than the midpoint value
        end = mid - 1

return -1  # not found
```

<br />

## Time Complexity

1. `Worst-Case Time Complexity`: O(log n)

   - In binary search, the search range is halved at each step. Thus, with n elements, it requires at most log n steps.

2. `Best-Case Time Complexity`: O(1)

   - If the target element is located at the midpoint, it can be found in the first comparison.

3. `Average Time Complexity`: O(log n)

   - In most cases, binary search operates with logarithmic time complexity, as the search range is halved at each step in the search process.