DSA 6: Binary Search Practice

1. Odd Array-Size [11,22,33,44,55,66,77]

arr = [11,22,33,44,55,66,77]
# [1 ]: l  .  t  m  .  .  r
# [2 ]: l  m  tr x  x  x  x
# [3 ]: x  x  ltr x  x  x  x
target = 33
l, r = 0, len(arr)-1  # r=6
ctr=0
found=False
while l<=r:
    ctr+=1
    print(f"[step {ctr}]: {arr[l:r+1]}")
    m=(l+r)//2
    if target == arr[m]:
        found=True
        print(f"Target:[{target}] found, index:[{m}] in {ctr} steps!")
        break
    elif target>arr[m]:
        l=m+1
    elif target<arr[m]:
        r=m-1
if not found:
    print(f"Target:[{target}] not found in {ctr} steps!")
    

[step 1]: [11, 22, 33, 44, 55, 66, 77]
[step 2]: [11, 22, 33]
[step 3]: [33]
Target:[33] found, index:[2] in 3 steps!

2. Even Array-Size [11,22,33,44,55,66,77,88]

arr = [11,22,33,44,55,66,77,88]
target = 33
l,r = 0, len(arr)-1

# [0 ]  l  .  t   .  .  .  .  r
# [1a]  l  .  t   m  .  .  .  r
# [1b]  l  .  trm x  x  x  x  x
# [2a]  l  m  tr  x  x  x  x  x
# [2b]  l  m  ltr x  x  x  x  x
# [3 ]  x  x  ltr x  x  x  x  x
found=False
ctr = 0
while l<=r:
    ctr+=1
    print(f"[{ctr}] Searching array: {arr[l:r+1]}, steps:[{ctr}]")
    m=(l+r)//2
    if target == arr[m]:
        found=True
        print(f"{target} found: index[{m}] in {ctr} steps")
        break
    elif target < arr[m]:
        r=m-1
    elif target > arr[m]:
        l=m+1
if not target:
    print(f"{target} not found: index[{m}] in {ctr} steps")

[1] Searching array: [11, 22, 33, 44, 55, 66, 77, 88], steps:[1]
[2] Searching array: [11, 22, 33], steps:[2]
[3] Searching array: [33], steps:[3]
33 found: index[2] in 3 steps

3. Binary Search Function

from typing import List
def binary_search_01(arr: List[int], target: int):
    ctr = 0
    l,r = 0, len(arr)-1
    
    while l <= r:
        print(f"Searching array: {arr[l:r+1]}")
        m = (l + r) // 2
        ctr+=1
        if target == arr[m]:
            print(f"{target} found on index [{m}] in {ctr} steps")
            return True
        elif target > arr[m]:
            l=m+1
        elif target < arr[m]:
            r=m-1

    print(f"{target} not found in {ctr} steps")
    return False

# arr = [11,22,33,44,55,66,77,88]
# [1 ]: m44 l55  66  77  r88
# [2a]:     l55 m66  77  r88
# [2b]:         m66 l77  r88
# [3a]:             l77m r88
binary_search_01([11,22,33,44,55,66,77,88],77)

Searching array: [11, 22, 33, 44, 55, 66, 77, 88]
Searching array: [55, 66, 77, 88]
Searching array: [77, 88]
77 found on index [6] in 3 steps

True