Exploring Sorting and Searching Algorithms With Golang — Binary Search

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. :)