Binary search in Python

Binary search is an efficient algorithm for finding a particular value in a sorted list or array of elements. The algorithm works by repeatedly dividing the search interval in half, and comparing the target value with the middle element of the interval. If the middle element is equal to the target value, the search is successful and the algorithm returns the index of the middle element. If the middle element is greater than the target value, the algorithm repeats the search on the lower half of the interval. If the middle element is less than the target value, the algorithm repeats the search on the upper half of the interval . This process is repeated until the target value is found or the search interval becomes empty.

Binary search can be implemented using two methods:

1. Iterative Binary Search method
2. Recursive Binary Search method

Iterative Binary Search in Python

In the iterative method, use a loop to repeatedly divide the search space into two halves and check whether the middle element of the current interval is the target element. If the middle element is equal to the target, then return its index. Otherwise, update the search interval to either the left or right half of the current interval, depending on whether the target is smaller or larger than the middle element. Repeat this process until you find the target element or the interval is empty.

Following is an example of the iterative binary search algorithm in action:

1. Searching for the value : 777
2. From the list : [111, 222, 333, 444, 555, 666, 777, 888, 999]

Step-by-step breakdown:

Following is a step-by-step breakdown of how the iterative binary search algorithm works:

1. Initialize two pointers, left and right, to the start and end of the list, respectively.

1. Enter a while loop that continues until left is greater than right. This loop represents the search space.

1. Inside the loop, calculate the index of the middle element of the current search space using the formula:

1. Check whether the middle element of the current search space is equal to the target element. If it is, return the index of the middle element.

1. If the middle element is less than the target, then update left to be mid + 1, since you know that the target, if present, must be in the right half of the current search space.

1. If the middle element is greater than the target, then update right to be mid - 1, since you know that the target, if present, must be in the left half of the current search space.

1. Repeat steps 3-6 until you either find the target element or the search space becomes empty (i.e., left is greater than right).

1. If the target element is not found, then return -1 to indicate that it is not present in the list.

In this case, the algorithm finds the target element at index 6 and returns it.

Recursive Binary Search in Python

In the recursive method, divide the search space into two halves and recursively search the left or right half until you find the target element or the interval is empty. The base case of the recursion is when the interval is empty, in which case you return -1 to indicate that the target is not found. The recursive function returns the index of the target element when it is found.

Following is an example of the recursive binary search algorithm in action:

Step-by-step breakdown:

Following is a step-by-step breakdown of how the recursive binary search algorithm works:

1. Suppose you have a sorted list of integers arr and you want to find the index of a target integer target:

1. Define a recursive function, binarySearch_Recursive(), that takes four arguments: the input array arr, the target integer target, the left and right indices of the current search space.

1. Inside the function, check whether the left index is greater than the right index. If it is, return -1 to indicate that the target is not found.

1. Otherwise, calculate the index of the middle element of the current search space using the formula:

1. Check whether the middle element of the current search space is equal to the target element. If it is, return the index of the middle element.

1. If the middle element is less than the target, recursively call the binarySearch_Recursive() function with updated arguments arr, target, mid + 1, and right, since you know that the target, if present, must be in the right half of the current search space.

1. If the middle element is greater than the target, recursively call the binarySearch_Recursive() function with updated arguments arr, target, left, and mid - 1, since you know that the target, if present, must be in the left half of the current search space.

1. Repeat steps 2-6 until you either find the target element or the search space becomes empty (i.e., left is greater than right).

1. If the target element is not found, you return -1 to indicate that it is not present in the list.

In this case, the algorithm finds the target element at index 6 and returns it.

Complexity in binary search

The time complexity of binary search is O(log n), where n is the number of elements in the sorted array.

This is because at each step of the algorithm, the search space is divided in half. In the worst case, you need to repeat this process until the search space is reduced to a single element. Since each division of the search space takes O(1) time, and you divide the search space in half at each step, the total number of steps required to reach a single element is proportional to log2(n), where n is the number of elements in the sorted array.

Therefore, the time complexity of binary search is O(log n).

The space complexity of binary search is O(1), since you only need to keep track of a few variables (e.g., the left and right indices of the current search space, and the middle index), and you do not need to create any additional data structures.

Complexity in Iterative and Recursive binary search

Both iterative and recursive binary search have the same time complexity of O(log n), where n is the size of the input array. However, the recursive method has a higher space complexity due to the recursive calls, which can lead to a stack overflow error if the input array is very large. In general, the iterative method is preferred for its simplicity and lower space complexity.