← Back to Index

📚 Single Element in a Sorted Array – Java Cheat Sheet

📌 What Is It?

The Single Element in a Sorted Array problem involves finding the single non-duplicate element in a sorted array where every other element appears exactly twice. The goal is to solve this in O(log N) time using binary search.

🧱 Pattern Template

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int left = 0, right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            // Ensure mid is even for comparison
            if (mid % 2 == 1) {
                mid--;
            }

            if (nums[mid] == nums[mid + 1]) {
                left = mid + 2; // Single element is in the right half
            } else {
                right = mid; // Single element is in the left half
            }
        }

        return nums[left]; // Single element
    }
}

📊 Time Complexity

• Binary Search: O(log N) – Halving the search space at each step.

✅ Use Cases

• Finding a unique element in a sorted array
• Applications in data deduplication

📘 Common LeetCode Problems

• 540. Single Element in a Sorted Array [Medium] Binary Search

🧪 Example: Single Element in a Sorted Array

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2

Explanation:
- The single non-duplicate element is 2.

▶️ View Animation

💡 Pro Tips

• Ensure the mid index is even for comparison with its pair.
• Edge cases: single-element arrays, arrays with all duplicates except one.
• Use binary search to efficiently narrow down the search space.