The binary search uses the divide and conquers approach, in which it divides the array into equal parts until it finds the target element.

A Binary search algorithm is implemented iterative as well as a recursive statement. Binary search is more efficient and faster as compared with linear search.

**Binary Search Algorithm**

- Sort and arrange the elements in the array
*arr*in ascending order. - The algorithms compare the middle element
*n*with the target element*target*. - The algorithm returns the position index of the middle element if the target element is found to be equal to the middle element,
- The algorithm searches the lower half of the array if the target element is less than the middle element.
- The algorithm searches the upper half of the array if the target element is greater than the middle element.
- The algorithm keeps repeating the 4th and 5th steps until the array’s length becomes one or less than 1.

By the end, either the index value of the element is returned, or the element doesn’t exist in the array.

**Binary search Pseudocode**

**Iterative**

left := 0

right:= n − 1

while left ≤ right do

middle := floor((left + right) / 2)

if arr[middle] target then

right := middle − 1

else:

return middle

return unsuccessful

**Recursive**

if right >= left

middle = (left+right)//2

if arr[middle] == target

return middle

else if arr[middle] > tarrget

return Binary_Search(arr, low, mid-1, target)

else

return Binary_Search(arr, mid+1, right, target)

else

return unsuccessful

**Implement Binary Search in Python**

**Iterative **

In the iterative approach, we use the loops to implement binary search.

left = 0

right = n-1

middle=0

while left<=right:

middle = (right+left)//2

#if the middle element is equal to the target element

if arr[middle]==target:

return middle

# if target element is greater than middle element

elif arr[middle]< target:

left = middle+1

# if target element is less than middle element

else:

right =middle-1

# if the target element is not present in the array

return -1

if __name__ == '__main__':

# sorted array

sorted_arr = [0,4,7,10,14,23,45,47,53]

# length of the array

n = len(sorted_arr)

#element to search

target = 47

position = Binary_Search(sorted_arr, n,target)

if position != -1:

print(f"Element {target} present at index {position}")

else:

print(f"Element {target} does not present in array")

**Output**

**Recursive**

In recursive instead of using loop, we keep calling the function again and again until the base condition get satisfied

#base condition

if righttarget:

return Binary_Search(arr, left, middle-1, target)

#if target element is smaller than middle element

else:

return Binary_Search(arr, middle+1, right, target)

if __name__ == '__main__':

# sorted array

sorted_arr = [0,4,7,10,14,23,45,47,53]

left=0

right = len(sorted_arr)-1

#element to search

target = 47

position = Binary_Search(sorted_arr, left, right,target)

if position != -1:

print(f"Element {target} present at index {position}")

else:

print(f"Element {target} does not present in array")

**Output**

**Complexity**

Binary search has a time complexity of O(log n), where **n **is the number of elements present in the array.

Binary search has a space complexity of O(1) because, in the algorithm, we are performing the in-place search.

**Conclusion **

Binary Search is one of the best and efficient searching algorithms. The time and space complexity of Binary search is also very low; the only prerequisite of binary search is, the input array should be sorted in ascending order.