Binary search

Binary search

Binary search algorithm is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array; if they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful. If the search ends with the remaining half being empty, the target is not in the array.

Overview

Binary search operates on the principle of dividing the search interval in half with each step. It can be implemented in two ways: iteratively or recursively. The algorithm assumes that the array is sorted in ascending or descending order. It is much more efficient than linear search for large arrays, as its time complexity is O(log n), where n is the number of elements in the array.

Algorithm

The binary search algorithm works as follows:

1. Find the middle element of the array.
2. If the middle element is equal to the target, the search is complete.
3. If the target is less than the middle element, repeat the search on the left subarray.
4. If the target is greater than the middle element, repeat the search on the right subarray.

This process is repeated until the target value is found or the subarray becomes empty.

Implementation

Pseudocode

The following is a pseudocode representation of the binary search algorithm:

``` function binarySearch(arr, target):

   left = 0
   right = arr.length - 1
   while left <= right:
       mid = left + (right - left) // 2
       if arr[mid] == target:
           return mid
       elif arr[mid] < target:
           left = mid + 1
       else:
           right = mid - 1
   return -1

```

Recursive Approach

The binary search algorithm can also be implemented recursively:

``` function recursiveBinarySearch(arr, left, right, target):

   if right >= left:
       mid = left + (right - left) // 2
       if arr[mid] == target:
           return mid
       elif arr[mid] < target:
           return recursiveBinarySearch(arr, mid + 1, right, target)
       else:
           return recursiveBinarySearch(arr, left, mid - 1, target)
   return -1

```

Applications

Binary search is used in a wide range of computing applications, including:

• Searching in databases
• Finding the position of an element in a sorted list
• In algorithms that require searching, such as finding the square root of a number
• In data compression

Complexity

The time complexity of binary search is O(log n), making it significantly more efficient for large datasets than a linear search, which has a time complexity of O(n). Its space complexity is O(1) for the iterative approach and O(log n) for the recursive approach due to the stack space used by recursion.

See Also

• Linear search
• Sorting algorithm
• Divide and conquer algorithm