What is Binary Search?

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

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.

from Linux Hint https://ift.tt/3vJPiS2