# Exploring Sorting and Searching Algorithms With Golang — Binary Search

**Binary Search** is defined as a searching algorithm used in a **sorted array** by **repeatedly dividing the search interval in half**. The idea of binary search is to use the information that the array is sorted and reduce the time complexity.

**Time Complexity**: O(log N)**Best Case :**O(1) , When the target element is found at the middle of the sorted array

It should have three inputs

- A sorted array
- Target value to search
- indices of the search range

Binary Search Algorithm can be implemented in 2 ways

- Iterative
- Recursive

**Iterative Binary Search Steps**

- Get the sorted array
- Compare the target value with the value at the middle index of the array
**Three cases**- If the target value is equal to the middle element, the search is successful, and returns the index of the middle element.
- If the target value is less than the middle element, update the ending index of the search range to be the middle index minus one and repeat the process from step 2.
- If the target value is greater than the middle element, update the starting index of the search range to be the middle index plus one and repeat the process from step 2.

**Code**

## Recursive Binary search Steps

- Get the sorted array
- Compare the
`left`

boundary exceeds the`right`

boundary, it indicates that the target element is not present within the current search space - Calculate the middle index
`mid`

within the current search space. It ensures that the middle index is computed without causing integer overflow issues, even for large values of`left`

and`right`

. - Check the element at the middle index
`mid`

matches the target value, the function returns`mid`

to indicate that the target element has been found. - If the element at
`mid`

is less than the target value, suggests that the target element must be in the right half of the current search space. Call the function recursively with an updated`left`

boundary (`mid+1`

) while keeping the`right`

boundary unchanged. - If the element at
`mid`

is greater than the target value, it implies that the target element is in the left half of the current search space. Call the function recursively with an updated`right`

boundary (`mid-1`

) while keeping the`left`

boundary unchanged. - The function uses a
`divide-and-conquer`

approach to recursively search for the target element in smaller and smaller sub arrays until the target is found or the search space is exhausted.

**Code**

## Slices Package

With latest golang release `1.21`

, introduced new package `slices`

which provides several common operations on slices .

As this package has the `BinarySearch`

function

## Conclusion

Binary search is a widely used algorithm in computer science that is used to search for an element in a sorted list of elements. It is an efficient algorithm that works by dividing the sorted data into two halves and examining the data at the point of the split. Binary search is a more specialized algorithm than sequential search as it takes advantage of data that has been sorted. It is a `“divide and conquer”`

algorithm that improves the search by recursively dividing the array.

**I hope this article helps. Thank you so much for reading. :)**