🧠 Finding the Single Element in a Sorted Array using Binary Search (C++)

Have you ever stumbled upon a coding problem that looked easy at first, but then turned into a brain teaser once you went deep into edge cases? That’s exactly what happened when I tried solving "Single Element in a Sorted Array" using C++ and binary search.

In this article, I’ll walk you through:

• The problem statement

• My solution with C++ code

• The issues I faced

• How I fixed them

• Key takeaways

---

🧩 Problem Statement

You are given a sorted array where every element appears exactly twice, except for one element that appears only once.

🔍 Your task is to find that single element in O(log n) time.

---

🧠 My Thought Process

We can easily solve this using linear search in O(n) time by comparing adjacent elements, but the real challenge lies in solving it using binary search in O(log n).

Let’s dive into the code and how it evolved:

---

✅ C++ Code with Binary Search

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int singleNonDuplicate(vector<int> &nums) {
        int low = 0, high = nums.size() - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;

            int rightLen = high - mid;
            int leftLen = mid - low;

            if (mid != low && nums[mid] == nums[mid - 1]) {
                if (leftLen % 2 == 0) {
                    high = mid - 2;
                } else {
                    low = mid + 1;
                }
            } else if (mid != high && nums[mid] == nums[mid + 1]) {
                if (rightLen % 2 == 0) {
                    low = mid + 2;
                } else {
                    high = mid - 1;
                }
            } else {
                return nums[mid];
            }
        }
        return nums[low];
    }
};

---

🐛 Challenges I Faced

This problem wasn’t as easy as it looked. Here are some key issues I encountered:

1. Index Out of Bounds

When comparing nums[mid] with nums[mid + 1] or nums[mid - 1], I didn’t initially check whether mid was at the start or end of the array. This caused segmentation faults.

✅ Fix: I added conditions to ensure mid != low and mid != high before comparing.

---

2. Wrong Search Direction

In some test cases like [1, 1, 2, 2, 3], my binary search was moving in the wrong direction and returning incorrect results like 2.

Here’s what went wrong:

• Mid was at index 2 (nums[mid] = 2)

• It matched with nums[mid + 1] = 2

• I moved only one step forward (low = mid + 1), which didn’t skip the entire pair.

✅ Fix: Instead of moving just one step, I moved two steps:

• low = mid + 2 or high = mid - 2
  This ensures we skip both elements in a matched pair and zero in on the single element.

---

🧠 Intuition Recap

• The array has all elements in pairs except one.

• If we use binary search and land on the first of a pair (nums[mid] == nums[mid + 1]), we know the single element must lie beyond that pair if the count of remaining elements on the right is even.

• If it's odd, the single lies on the left.

This parity-based logic helps narrow down the position of the single element in logarithmic time!

---

✅ Output Example

Input: [1,1,2,2,3]
Output: 3

---

📌 Final Thoughts

This problem was deceptively tricky — it taught me that binary search is not just about halving the array, but about reading patterns in how data is structured.

If you’re learning DSA like I am, I highly recommend solving this one and writing about your thought process. It makes the learning permanent.

---

✨ Follow My Dev Journey

I’m sharing my journey through:

• 🔧 Web Development Projects

• 🔁 DSA Problems & Patterns

• 🤖 AI/ML Learning (coming soon!)

If this helped you — drop a like, share it with your DSA buddies, and feel free to connect.

Let’s grow together 🌱

📍 Connect with me:
GitHub | LinkedIn