28.6 C
Jaipur
Monday, June 21, 2021

# What is Binary Search? – Linux Hint

### Rewards, quests, other details revealed

A binary search is a searching algorithm used to search target elements in a container where elements must be arranged in ascending order. Generally, binary search is used to search the index number of the target element in a sorted array.

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

1. Sort and arrange the elements in the array arr in ascending order.
2. The algorithms compare the middle element n with the target element target.
3. The algorithm returns the position index of the middle element if the target element is found to be equal to the middle element,
4. The algorithm searches the lower half of the array if the target element is less than the middle element.
5. The algorithm searches the upper half of the array if the target element is greater than the middle element.
6. 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

function Binary_Search(arr, n, target) is
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

function Binary_Search(arr, left, right, target) is

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.

def Binary_Search(arr,n, target):
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
return1

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

Element 47 present at index 7

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

def Binary_Search(arr,left,right ,target):
#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

Element 90 is not present in the array

## 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.