DSA - Binary Search

Binary Search is a search technique to find elements in a collection.

note:

Binary search only works on sorted collections

example:

this's a sorted array

10,11,12,13,14,15

## the index of this array will be 
0,1,2,3,4,5

say, we want to find element 13, initial thought will be to just loop over the array and search for it. (That's linear search)

We can use the fact that our array is sorted to dramatically decrease our window of search. Imagine at the starting point, hypothetically we standing on element 12, since we know that the array is sorted already we know for a fact that13 can't come before 12.

we'll only put our effort into searching for the element after 12.

setps:

• initialize 2 pointers, start the beginning of the array, end at the end of the array
• Find the elements at the middle of 2 pointers
• if the element at the middle is bigger than our goal, set the endpoint to the middle. if the middle is bigger than our target value, that means there's no point in searching for an element that comes in the middle.
• if the element at the middle is smaller than our goal, set the start point to middle +1

let's still look at the previous array example:

10,11,12,13,14,15

start = 0
end = 5
mid = (0+5) / 2 = 2

## iteration 1:
target = 15
current = 12

12 is smaller than our target, our target is 15. so we'll set the start pointer to mid + 1. so we'll have this

## iteration 2:
start = 3
end = 5
mid = (3+5) / 2 = 4
target = 15
current = 14

## iteration 3:
start = 4 + 1 = 5
end = 5
mid = (5+5) / 2 = 5

target = 15
current = 15

Binary search code implementation

import math

def binary_search(arr,target):
left = 0
right = len(arr) -1

while (left < right):
   mid= math.floor((left + right) / 2)
   if arr[mid] == target:
   return mid

   if arr[mid] < target:
      left = mid + 1
   else:
      right = mid - 1
return -1

arr = [1,2,3,4,5,6,7,8]
target = 5
result = binary_search(arr, target)

if result != -1:
    print(f"index of the targeted element is {result}")

else:
    print("target element index is not found")