** Problem: **We have a sorted array and a key element, we need to find out if the key element is present in the array. If it exists return the index of that element or return -1 if it doesn't exist. If the array has repeated
elements, the order of the index is not important.

Example:

__Pseudocode:__
Step 1: Initialise low = 0, high = array.count - 1

Step 2: Run a loop until low <= high

Step 3: Compute middle index

middle = (low +
high) / 2

Step 4: If array[middle] == x, we found the index, then

return x

Step 5: If x < array[middle], x lies in the first half of the
array, then

high = middle - 1

repeat from step 2

Step 6: If x > array[middle], x lies in the second half of the array,
then

low = middle + 1

repeat from step 2

Step 7: return -1, as x is not present in the array

__Iterative Binary Search:__` ````
func binarySearch(array:[Int],x:Int,n:Int)->Int{ var low = 0, high = n
while low <= high { let mid = (low + high) / 2 if array[mid] == x{ return mid }else if x < array[mid]{ high = mid - 1 }else{ low = mid + 1 } } return -1}
```

__Recursive Binary Search:__```
func binarySearch(array:[Int],x:Int,low:Int,high:Int)->Int{ if low > high { return -1 }
let mid = (low + high) / 2 if array[mid] == x{ return mid }else if x < array[mid]{ return binarySearch(array: array, x: x, low: low, high: mid - 1) } return binarySearch(array: array, x: x, low: mid + 1, high: high)}
```

__Time Complexity of Iterative Binary Search__Let's say the iteration in Binary Search terminates after k iterations.

At each iteration, the array is divided by half.

Length of array = n

Iteration 1: Length of array = n

Iteration 2: Length of array = n / 2

Iteration 3: Length of array = (n / 2) / 2 = n / 2²

.

.

.

Iteration k: Length of array = n / 2k

We can not divide the array further because at Iteration k, array contains only one element.

so at,

Iteration k: length of array = 1 = n / 2k

=> 1 = n / 2k

=> n = 2k

Applying log function on both sides

=> log2 (n) = log2 (2k)

=> log2 (n) = log2 (2k)

=> log2 (n) = k log2 (2)

=> log2 (n) = k ∵ log2 (2) = 1

∴ k = log2 (n)

Hence Time complexity of Binary search = log2 (n)

__Space Complexity__**:**

__of Iterative Binary Search__ O(1) for maintaining function call stack

__Time Complexity of Recursive Binary Search__Recurrence Relation:

At each recursion, array is being divided by half.

i.e. n => n/2 => n/4 => n/8......

Since we are interested in only one recursion we'll consider

T(n) = T(n/2) + c where c is conditions or mid calculation..

T(n) = T(n/2)+c if n > 1

1 if n = 1

**Time Complexity using Substitution method:**

Step 1: T(n) = T(n/2) + c

Step 2: T(n/2) = T(n/4) + c

Step 3: T(n/4) = T(n/8) + c

Substitute T(n/2) in Step-1

=> T(n) = T(n/4) + c + c = T(n/2²) + 2c

Substitute T(n/4) in above

=> T(n) = T(n/8) + c + 2c = T(n/23) + 3c

=> = T(n/24) + 4c

=> = T(n/25) + 5c

.

.

.

at kth step

=> T(n) = T(n/2k) + kc

.

.

.

Recursive call will stop when length of array = 1 => n = 1 => T(1) = 1

In the above equation, to get T(1) we'll consider n = 2k

=> T(n) = T(2k / 2k ) + kc

=> T(n) = T(1) + kc

=> T(n) = 1 + kc

Since n = 2k, take log on both sides

=> log2 n = k log2 2

=> k = log2 n

∴ Substitute k in above equation

=> T(n) = 1 + log2 n * c

=> T(n) = log2 n

So Time complexity is O(log n)

__Space Complexity of__

__Recursive Binary Search__

__:__O(log n) for maintaing function call stack

## Comments

## Post a Comment