Summary of "BS-8. Single Element in Sorted Array"

Summary of “BS-8. Single Element in Sorted Array”

This video explains how to find the single element in a sorted array where every other element appears exactly twice. The problem is a common interview question and is part of a binary search series.

---

Problem Statement

• Given a sorted array of integers.
• Every element appears exactly twice except one single element which appears once.
• The array is sorted, so pairs appear consecutively.
• Goal: Find the single element that appears once.

---

Brute Force Approach

• Iterate through the array.
• For each element at index i, check:
  • If i == 0, compare with the next element.
  • If i == n-1, compare with the previous element.
  • Otherwise, check both neighbors.
• If the element does not match either neighbor, it is the single element.
• Time complexity: O(n)
• Edge case: If array size is 1, return that element immediately.
• Important: Handle boundary conditions carefully to avoid out-of-bound errors.

---

Need for Optimization

• Interviewers expect better than O(n).
• Since the array is sorted, binary search can be applied.
• Binary search requires a way to eliminate half the search space based on a property of the single element.

---

Key Observations for Binary Search

• Elements appear in pairs, so their indices have a pattern:
  • Before the single element:
    • The first of the pair is at an even index.
    • The second of the pair is at an odd index.
  • After the single element:
    • The pattern flips (pairs start at odd indices).
• Using this, you can determine if you are on the left or right half of the single element.

---

Binary Search Methodology

1. Trim search space:

   • Exclude the first and last elements initially to avoid boundary checks.
   • Check separately if the first or last element is the single element.

2. Binary search loop:

   • Calculate mid = (low + high) // 2.
   • Check if arr[mid] is the single element by verifying:
     • arr[mid] != arr[mid - 1] and arr[mid] != arr[mid + 1].
   • If yes, return arr[mid].

3. Elimination logic:

   • If mid is even and arr[mid] == arr[mid + 1], then the single element is in the right half; eliminate left half by moving low = mid + 2.
   • If mid is odd and arr[mid] == arr[mid - 1], then the single element is in the right half; eliminate left half by moving low = mid + 1.
   • Otherwise, eliminate the right half by moving high = mid - 1.

4. Repeat until the single element is found.

---

Why This Works

• The pattern of pairs changes after the single element.
• Using index parity and neighbor comparisons, you can determine which half to eliminate.
• This reduces the search space by half each iteration.

---

Edge Cases

• Array of size 1.
• Single element at the beginning or end of the array.
• Make sure to handle boundary conditions separately to avoid index errors.

---

Complexity

• Time Complexity: O(log n) due to binary search.
• Space Complexity: O(1).

---

Summary of Steps to Solve Using Binary Search

• Step 1: Check if first or last element is single element.
• Step 2: Initialize low = 1, high = n - 2.
• Step 3: While low <= high:
  • Calculate mid = (low + high) // 2.
  • If arr[mid] is single element (not equal to neighbors), return it.
  • Else determine half to eliminate:
    • If (mid % 2 == 0 and arr[mid] == arr[mid + 1]) or (mid % 2 == 1 and arr[mid] == arr[mid - 1]), move low = mid + 1.
    • Else move high = mid - 1.
• Step 4: Return -1 (dummy return, logically unreachable).

---

Additional Notes

• The instructor emphasizes writing clean, readable code.
• Trimming the search space avoids complicated boundary checks.
• Maintaining consistent binary search conditions (low <= high) helps avoid bugs.
• The approach is part of the Striver’s A to Z DSA course.

---

Speakers / Sources

• The video features Striver, a well-known educator in Data Structures and Algorithms.
• No other speakers or sources are explicitly mentioned.

---

If you want to practice this problem, the video description contains a link to the problem statement and code editor.

Category

Educational

---

Share this summary

Share on X/Twitter Share on Facebook Share on LinkedIn Share on Reddit Share on WhatsApp Share on Telegram

---

Is the summary off?

If you think the summary is inaccurate, you can reprocess it with the latest model.

Reprocess summary

Video