What’s Wrong with Binary Search?

Hi everyone, Oleksiy Chebotarov here. I’ve been grinding on LeetCode for quite some time now (you can check my profile here: https://leetcode.com/u/capitan112/), and I’ve solved over 700 problems. While working on binary search problems, I noticed something interesting. Most of the solutions I came across used a "standard" binary search implementation, but I couldn’t help but notice some recurring issues with it. Today, I want to share my thoughts on what’s wrong with the typical binary search implementation and how I approached solving these problems with my own version.

The "Standard" Binary Search Algorithm.

First, let’s look at the classic binary search implementation in Swift:

```swift
func binarySearch(nums: [Int], target: Int) -> Int {
    var left = 0
    var right = nums.count - 1
    
    while left <= right {
        let mid = left + (right - left) / 2
        
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    return -1
}
```        

At first glance, this implementation seems fine. It’s widely used in tutorials and competitive programming. However, it has several issues that make it suboptimal. You can find the classical solution and explanation on Leetcode here: Leetcode Binary Search Editorial.

Problems with the Standard Binary Search:

?? Edge Cases Handling – The classic implementation struggles with certain edge cases. What happens when the array has only one element? What if the target is smaller than the smallest element or larger than the largest one? These cases often require additional handling.

?? Index Overflow – The calculation of mid = left + (right - left) / 2 is designed to prevent overflow, but for large indices (especially in languages without built-in safety like C/C++), incorrect implementations may still cause overflow errors. (Yes, this is not valid for Swift.)

?? Inconsistent Behavior with Duplicates – The standard implementation finds one occurrence of the target value, but if there are duplicates, it does not guarantee finding the first or last occurrence, which can be crucial in many problems.

?? Unclear Logic for Lower and Upper Bound Searches – Many problems require finding the first or last position of an element rather than just checking its presence. The standard implementation requires additional tweaks to handle these variations.

Better Approach to Binary Search.

After encountering these issues, I started looking for a more robust and efficient approach to binary search. During my exploration, I came across an alternative implementation that addresses many of the shortcomings of the classic version. Here’s what I found:

```swift
func binarySearch(nums: [Int], target: Int) -> Int {
    if nums.count == 1 && target == nums[0] {
        return 0
    }
    
    var bad = -1
    var good = nums.count
    
    while good - bad > 1 {
        let middle = bad + (good - bad) / 2
        
        if nums[middle] >= target {
            good = middle
        } else {
            bad = middle
        }
    }
    
    if good != nums.count && nums[good] == target {
        return good
    }
    
    return -1
}
```        

Advantages of This Approach`

? More Robust Edge Case Handling – This implementation properly handles single-element arrays, cases where the target is smaller/larger than any element, and ensures correctness even in small arrays.

? Clearer Boundaries – The use of bad and good variables makes it explicit that bad represents an invalid state while good points to a potential solution.

? Guaranteed First Occurrence – Unlike the standard implementation, this approach ensures that if the target exists in the array, it returns the first occurrence (useful in problems requiring lower bound searches).

? Avoids Infinite Loops – Since the condition good - bad > 1 ensures we always move towards a solution, it naturally prevents infinite loops that sometimes occur in improperly implemented binary searches.

? Finding the Insertion Point

One of the key advantages of this approach is its ability to find the insertion point for an element if it’s not present in the array. This is particularly useful in scenarios where you need to maintain a sorted array or perform operations like inserting elements in the correct position.

For example: If the target is not found, good will point to the index where the target should be inserted to keep the array sorted. This eliminates the need for additional logic to determine the insertion point, making the algorithm more versatile.

Real-World Applications: This implementation is particularly useful in scenarios where you need to: Find the insertion point for a target in a sorted array. Handle edge cases like empty arrays or single-element arrays. Avoid bugs related to infinite loops or incorrect boundary updates.

Final Thoughts

Binary search is a fundamental algorithm, but it’s easy to get it wrong if you’re not careful. By tweaking the classic implementation, I was able to address some of its shortcomings and create a more robust solution. If you’re working on binary search problems, I encourage you to think critically about edge cases and test your implementation thoroughly.

If you’re interested in discussing more algorithmic problems or sharing your own insights, feel free to connect with me on LeetCode (https://leetcode.com/u/capitan112/) or LinkedIn. Let’s keep learning and improving together!

What do you think about this approach? Have you encountered similar issues with binary search? Let’s discuss in the comments! ??

Tags

#BinarySearch #Algorithms #Swift #Programming #LeetCode #Coding #SoftwareEngineering #ProblemSolving #Tech #Developers #CodeOptimization #EdgeCases #LearningToCode