Binary Search

Algorithm 1: Linear Search (Time Complexity: O(n))

Algorithm 2: Binary Search (Time Complexity: O(logn))

- Given Array must be sorted.

#Using Iteration

BinSearch(A,v):
low=0, high=(n-1)
while low<=high do
    mid=(low+high)/2
    if A[mid] == v then
        return mid
    else if A[mid] < v then
        low = mid+1
    else
        high = mid-1
return -1

#Using Recursion

BinSearch(A,v):
return BinSearchHelper(A,0,n-1,v)
    
BinSearchHelper(A,low,high,v):
if low > high then
    return -1
mid = (low+high)/2
if A[mid] == v then
    return mid
else if A[mid] < v then
    BinSearchHelper(A,mid+1,high,v)
else
    BinSearchHelper(A,low,high-1,v)