Binary Search

Binary search is a search algorithm that works on sorted arrays or lists. It starts by comparing the target value to the middle element of the array. If the target value is equal to the middle element, the algorithm returns the index of the middle element. If the target value is less than the middle element, the algorithm searches the left half of the array. If the target value is greater than the middle element, the algorithm searches the right half of the array. The algorithm repeats this process until the target value is found or the search range is exhausted.

Binary search is a search algorithm used to find the position of a target value within a sorted array or list. The algorithm begins by comparing the target value to the middle element of the array. If the target value is equal to the middle element, the algorithm returns the index of the middle element. If the target value is less than the middle element, the algorithm repeats the process on the left half of the array. If the target value is greater than the middle element, the algorithm repeats the process on the right half of the array.

This process of dividing the search range in half is repeated until the target value is found or the search range is exhausted. If the target value is not present in the array, the algorithm eventually reaches a point where the search range is empty, and the target value is not found.

Binary search has a time complexity of O(log n) where n is the size of the array. This makes it an efficient algorithm for searching large sorted arrays, as it can quickly narrow down the search range by eliminating half of the remaining elements at each iteration. However, binary search requires that the array be sorted, which can add an additional time complexity of O(n log n) if the array is unsorted and needs to be sorted first.

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

In this algorithm, arr is the sorted array to search, and target is the value to find. The algorithm starts by setting low and high to the first and last indices of the array. The algorithm then enters a loop that continues as long as low is less than or equal to high. In each iteration of the loop, the algorithm calculates the middle index mid, compares the middle element arr[mid] to the target value, and updates the search range accordingly. If the middle element is equal to the target value, the algorithm returns the index of the middle element. If the target value is less than the middle element, the algorithm updates high to be mid - 1, effectively searching the left half of the array. If the target value is greater than the middle element, the algorithm updates low to be mid + 1, effectively searching the right half of the array. If the loop completes without finding the target value, the algorithm returns -1.