Binary Search Algorithm - Explanation

Binary Search Algorithm is an efficient algorithm to find a target element in a sorted array. It repeatedly divides the array into half until the target element is found. We will use an example array of [5, 8, 10, 15, 21, 35, 47, 89, 125, 345] and see how it works when searching for the element 35.

Step 1: Initialize two pointer indexes

We set two pointer indexes: L at the start of the array (L = 0) and R at the end of the array (R = len(arr) - 1). For example, with our array of 10 elements, L = 0 and R = 9.

Step 2: Calculate the middle index

The middle index, M, is determined using the formula (L + R) // 2. Here, M = (0 + 9) // 2 = 4, which represents the index of the middle element in the current array range.

Step 3: Compare the middle element with the target element

if M is less than the targetted number 35, then L needs to be moved to index where M resides, or else if M is bigger than the targetted number, R needs to be moved where our targetted number resides. Since current nums[M] is 21 which less than the targetted number then L is moved to M.

Step 4: Continuing steps 1-3 until the target element is found

We will find the next middle number M = (L + R) // 2 = (4 + 9) // 2 = 6

Step 5: Redefine the middle index again

Since the middle index M holds a value greater than the target, we update R to M.

Step 6: Find the target again, and return the index

We move M to M = (L+R) // 2 = (4 + 6 ) // 2 = 5, then we got the middle index coincides with the target. then, we need to return idx = 5

Step 7: Handling Edge Cases

If the loop exits without finding the target (L > R), return -1 to indicate that the target is not in the array.

The complete python code for binary search algorithm can be shown below:

nums = [5,8,10,15, 21, 35, 47, 89, 125, 345]
target = 47 



def binarySearch(nums, target): 
    L = 0 
    R = len(nums) - 1

    while L <= R: 
        M = (L + R) // 2
        if nums[M] == target: 
            return M 
        elif nums[M] < target: 
            L = M + 1
        else: 
            R = M - 1

    return -1


print(binarySearch(nums, target))