Find K Closest Elements

🎯

Find K Closest Elements

mediumBINARY_SEARCHGoogleAmazonFacebook

Imagine you are building a location-based app that suggests the closest stores to a user’s current location. You want to efficiently find the K stores closest to a given point from a sorted list of store locations.

💡 This problem is about searching in a sorted array to find a subset of elements closest to a target. Beginners often struggle because it’s not a straightforward binary search for a single element, but rather finding a boundary or window that satisfies a distance condition. Understanding how to apply binary search to find boundaries rather than exact matches is key.

📋

Problem Statement

Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order. An integer a is closer to x than an integer b if: |a - x| < |b - x|, or |a - x| == |b - x| and a < b.

1 ≤ k ≤ arr.length1 ≤ arr.length ≤ 10^5-10^4 ≤ arr[i], x ≤ 10^4arr is sorted in ascending order

💡

Example

Input"arr = [1,2,3,4,5], k = 4, x = 3"

Output[1,2,3,4]

The four closest elements to 3 are 1, 2, 3, and 4.

Input"arr = [1,2,3,4,5], k = 4, x = -1"

Output[1,2,3,4]

Even though -1 is less than all elements, the closest k elements are the first four.

• x is smaller than all elements → return first k elements
• x is larger than all elements → return last k elements
• k equals the length of the array → return entire array
• arr contains duplicates → still return closest k elements sorted

⚠️

Common Mistakes

Comparing absolute distances incorrectly (e.g., not handling tie-breaker a < b)

Incorrect window chosen, failing test cases with equal distances

✅ Use the problem’s tie-breaker rule explicitly when comparing distances

Using sum of distances of window edges instead of comparing edges separately

Wrong window chosen because sum can be misleading

✅ Compare distances at edges individually as in the binary search condition

Off-by-one errors in binary search boundaries

Infinite loops or incorrect window start index

✅ Carefully set low = 0 and high = n-k and use while (low < high)

Not returning the window sorted or returning wrong slice

Output not sorted or wrong elements returned

✅ Return arr[low:low+k] which is guaranteed sorted since arr is sorted

🧠

Brute Force (Sliding Window Check)

💡 Starting with brute force helps understand the problem deeply by checking all possible windows of size k and comparing their closeness to x. Though inefficient, it builds intuition about what 'closest' means and how to compare windows.

Intuition

Check every contiguous subarray of length k and find which one has the smallest distance to x by comparing the edges using the problem's tie-breaker rule. Return the first such subarray.

Algorithm

1. Initialize a variable to track the minimum distance and the starting index of the best window.
2. Iterate over all windows of size k in the array.
3. For each window, compare the distances of the left and right edges to x using the problem's tie-breaker rule.
4. Update the best window if the current window is closer to x.
5. Return the subarray starting at the best window index.

💡 This approach is straightforward but requires checking many windows, which is inefficient for large arrays.

</>

Code

from typing import List

def findClosestElements(arr: List[int], k: int, x: int) -> List[int]:
    n = len(arr)
    best_start = 0
    for start in range(n - k + 1):
        left = arr[start]
        right = arr[start + k - 1]
        # Compare distances with tie-breaker
        if start == 0:
            best_start = 0
            continue
        prev_left = arr[best_start]
        prev_right = arr[best_start + k - 1]
        # Compare current window edges with best window edges
        # If current window is closer, update best_start
        # Use problem's tie-breaker: compare left edges first, then right edges
        def is_closer(l1, r1, l2, r2, x):
            dist1_left = abs(l1 - x)
            dist2_left = abs(l2 - x)
            if dist1_left < dist2_left:
                return True
            elif dist1_left > dist2_left:
                return False
            else:
                if l1 < l2:
                    return True
                elif l1 > l2:
                    return False
                else:
                    dist1_right = abs(r1 - x)
                    dist2_right = abs(r2 - x)
                    if dist1_right < dist2_right:
                        return True
                    elif dist1_right > dist2_right:
                        return False
                    else:
                        return r1 < r2
        if is_closer(left, right, prev_left, prev_right, x):
            best_start = start
    return arr[best_start:best_start + k]

# Driver code
if __name__ == '__main__':
    print(findClosestElements([1,2,3,4,5], 4, 3))  # Output: [1,2,3,4]

Line Notes

n = len(arr)Calculate array length to know how many windows to check

for start in range(n - k + 1)Iterate over all possible windows of size k

# Compare distances with tie-breakerUse problem's tie-breaker rule to compare closeness of windows

if is_closer(left, right, prev_left, prev_right, x)Update best window if current window is closer

import java.util.*;

public class Solution {
    public static List<Integer> findClosestElements(int[] arr, int k, int x) {
        int n = arr.length;
        int bestStart = 0;
        for (int start = 0; start <= n - k; start++) {
            int left = arr[start];
            int right = arr[start + k - 1];
            if (start == 0) {
                bestStart = 0;
                continue;
            }
            int prevLeft = arr[bestStart];
            int prevRight = arr[bestStart + k - 1];
            if (isCloser(left, right, prevLeft, prevRight, x)) {
                bestStart = start;
            }
        }
        List<Integer> result = new ArrayList<>();
        for (int i = bestStart; i < bestStart + k; i++) {
            result.add(arr[i]);
        }
        return result;
    }

    private static boolean isCloser(int l1, int r1, int l2, int r2, int x) {
        int dist1Left = Math.abs(l1 - x);
        int dist2Left = Math.abs(l2 - x);
        if (dist1Left < dist2Left) return true;
        else if (dist1Left > dist2Left) return false;
        else {
            if (l1 < l2) return true;
            else if (l1 > l2) return false;
            else {
                int dist1Right = Math.abs(r1 - x);
                int dist2Right = Math.abs(r2 - x);
                if (dist1Right < dist2Right) return true;
                else if (dist1Right > dist2Right) return false;
                else return r1 < r2;
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(findClosestElements(new int[]{1,2,3,4,5}, 4, 3)); // [1, 2, 3, 4]
    }
}

Line Notes

int n = arr.length;Get array length for window iteration

for (int start = 0; start <= n - k; start++)Loop over all windows of size k

if (isCloser(left, right, prevLeft, prevRight, x))Update best window start index if current window is closer

List<Integer> result = new ArrayList<>();Prepare list to return the closest elements

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

bool isCloser(int l1, int r1, int l2, int r2, int x) {
    int dist1Left = abs(l1 - x);
    int dist2Left = abs(l2 - x);
    if (dist1Left < dist2Left) return true;
    else if (dist1Left > dist2Left) return false;
    else {
        if (l1 < l2) return true;
        else if (l1 > l2) return false;
        else {
            int dist1Right = abs(r1 - x);
            int dist2Right = abs(r2 - x);
            if (dist1Right < dist2Right) return true;
            else if (dist1Right > dist2Right) return false;
            else return r1 < r2;
        }
    }
}

vector<int> findClosestElements(vector<int>& arr, int k, int x) {
    int n = arr.size();
    int bestStart = 0;
    for (int start = 0; start <= n - k; start++) {
        int left = arr[start];
        int right = arr[start + k - 1];
        if (start == 0) {
            bestStart = 0;
            continue;
        }
        int prevLeft = arr[bestStart];
        int prevRight = arr[bestStart + k - 1];
        if (isCloser(left, right, prevLeft, prevRight, x)) {
            bestStart = start;
        }
    }
    return vector<int>(arr.begin() + bestStart, arr.begin() + bestStart + k);
}

int main() {
    vector<int> arr = {1,2,3,4,5};
    vector<int> res = findClosestElements(arr, 4, 3);
    for (int num : res) cout << num << ' ';
    cout << endl;
    return 0;
}

Line Notes

int n = arr.size();Determine array size for iteration limits

for (int start = 0; start <= n - k; start++)Check every window of size k

if (isCloser(left, right, prevLeft, prevRight, x))Update best window if current window is closer

return vector<int>(arr.begin() + bestStart, arr.begin() + bestStart + k);Return the closest k elements

function isCloser(l1, r1, l2, r2, x) {
    const dist1Left = Math.abs(l1 - x);
    const dist2Left = Math.abs(l2 - x);
    if (dist1Left < dist2Left) return true;
    else if (dist1Left > dist2Left) return false;
    else {
        if (l1 < l2) return true;
        else if (l1 > l2) return false;
        else {
            const dist1Right = Math.abs(r1 - x);
            const dist2Right = Math.abs(r2 - x);
            if (dist1Right < dist2Right) return true;
            else if (dist1Right > dist2Right) return false;
            else return r1 < r2;
        }
    }
}

function findClosestElements(arr, k, x) {
    let n = arr.length;
    let bestStart = 0;
    for (let start = 0; start <= n - k; start++) {
        let left = arr[start];
        let right = arr[start + k - 1];
        if (start === 0) {
            bestStart = 0;
            continue;
        }
        let prevLeft = arr[bestStart];
        let prevRight = arr[bestStart + k - 1];
        if (isCloser(left, right, prevLeft, prevRight, x)) {
            bestStart = start;
        }
    }
    return arr.slice(bestStart, bestStart + k);
}

// Test
console.log(findClosestElements([1,2,3,4,5], 4, 3)); // [1,2,3,4]

Line Notes

let n = arr.length;Get array length to know how many windows to check

for (let start = 0; start <= n - k; start++)Iterate over all possible windows of size k

if (isCloser(left, right, prevLeft, prevRight, x))Update best window start if current window is closer

return arr.slice(bestStart, bestStart + k);Return the closest k elements

⏱

Complexity

TimeO(n*k)

SpaceO(k)

We check all n-k+1 windows, each of size k, so roughly O(n*k). Space is O(k) for the output.

💡 For n=1000 and k=10, this means about 10,000 operations, which is slow for large n.

Interview Verdict: TLE / Inefficient for large inputs

This approach is too slow for large arrays but is useful to understand the problem and correctness.

🧠

Two Pointer Sliding Window

💡 This approach improves efficiency by using two pointers to shrink the window from both ends based on closeness to x, avoiding checking all windows explicitly.

Intuition

Start with the entire array as a window and shrink it from the side that is farther from x until the window size is k.

Algorithm

1. Initialize two pointers at the start and end of the array.
2. While the window size is greater than k, compare the distances of the elements at the edges to x.
3. Remove the element farther from x by moving the corresponding pointer inward.
4. Return the subarray between the two pointers.

💡 This approach is more efficient because it only shrinks the window until size k, avoiding unnecessary checks.

</>

Code

from typing import List

def findClosestElements(arr: List[int], k: int, x: int) -> List[int]:
    left, right = 0, len(arr) - 1
    while right - left + 1 > k:
        if abs(arr[left] - x) > abs(arr[right] - x):
            left += 1
        else:
            right -= 1
    return arr[left:right+1]

# Driver code
if __name__ == '__main__':
    print(findClosestElements([1,2,3,4,5], 4, 3))  # Output: [1,2,3,4]

Line Notes

left, right = 0, len(arr) - 1Initialize pointers to cover entire array

while right - left + 1 > kShrink window until size k

if abs(arr[left] - x) > abs(arr[right] - x)Remove element farther from x on left side

return arr[left:right+1]Return the final window of size k

import java.util.*;

public class Solution {
    public static List<Integer> findClosestElements(int[] arr, int k, int x) {
        int left = 0, right = arr.length - 1;
        while (right - left + 1 > k) {
            if (Math.abs(arr[left] - x) > Math.abs(arr[right] - x)) {
                left++;
            } else {
                right--;
            }
        }
        List<Integer> result = new ArrayList<>();
        for (int i = left; i <= right; i++) {
            result.add(arr[i]);
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(findClosestElements(new int[]{1,2,3,4,5}, 4, 3)); // [1, 2, 3, 4]
    }
}

Line Notes

int left = 0, right = arr.length - 1;Start pointers at array boundaries

while (right - left + 1 > k)Loop until window size is k

if (Math.abs(arr[left] - x) > Math.abs(arr[right] - x))Remove element farther from x on left

for (int i = left; i <= right; i++)Collect elements in the final window

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

vector<int> findClosestElements(vector<int>& arr, int k, int x) {
    int left = 0, right = arr.size() - 1;
    while (right - left + 1 > k) {
        if (abs(arr[left] - x) > abs(arr[right] - x)) {
            left++;
        } else {
            right--;
        }
    }
    return vector<int>(arr.begin() + left, arr.begin() + right + 1);
}

int main() {
    vector<int> arr = {1,2,3,4,5};
    vector<int> res = findClosestElements(arr, 4, 3);
    for (int num : res) cout << num << ' ';
    cout << endl;
    return 0;
}

Line Notes

int left = 0, right = arr.size() - 1;Initialize pointers at array ends

while (right - left + 1 > k)Shrink window until size k

if (abs(arr[left] - x) > abs(arr[right] - x))Remove element farther from x on left

return vector<int>(arr.begin() + left, arr.begin() + right + 1);Return the final window slice

function findClosestElements(arr, k, x) {
    let left = 0, right = arr.length - 1;
    while (right - left + 1 > k) {
        if (Math.abs(arr[left] - x) > Math.abs(arr[right] - x)) {
            left++;
        } else {
            right--;
        }
    }
    return arr.slice(left, right + 1);
}

// Test
console.log(findClosestElements([1,2,3,4,5], 4, 3)); // [1,2,3,4]

Line Notes

let left = 0, right = arr.length - 1;Set pointers to array boundaries

while (right - left + 1 > k)Continue until window size is k

if (Math.abs(arr[left] - x) > Math.abs(arr[right] - x))Remove element farther from x on left

return arr.slice(left, right + 1);Return the final window

⏱

Complexity

TimeO(n)

SpaceO(k)

We shrink the window from size n to k by moving pointers inward, so O(n) time. Space is O(k) for output.

💡 For n=1000 and k=10, this means about 1000 operations, much faster than brute force.

Interview Verdict: Accepted but can be improved

This approach is efficient enough for many cases but not optimal for very large arrays.

🧠

Binary Search on Left Boundary (Optimal)

💡 This approach uses binary search to find the optimal left boundary of the window of size k, leveraging the sorted property and the problem’s distance condition. It’s the most efficient and elegant solution.

Intuition

The k closest elements form a contiguous window. We binary search the start index of this window by comparing distances at the edges to decide which side to move.

Algorithm

1. Set low = 0 and high = n - k (possible start indices).
2. While low < high, compute mid = (low + high) // 2.
3. Compare distance between x and arr[mid] with distance between arr[mid + k] and x.
4. If arr[mid] is farther, move low to mid + 1; else move high to mid.
5. Return the subarray starting at low of length k.

💡 Binary searching the window start reduces the search space logarithmically, making it very efficient.

</>

Code

from typing import List

def findClosestElements(arr: List[int], k: int, x: int) -> List[int]:
    low, high = 0, len(arr) - k
    while low < high:
        mid = (low + high) // 2
        if x - arr[mid] > arr[mid + k] - x:
            low = mid + 1
        else:
            high = mid
    return arr[low:low + k]

# Driver code
if __name__ == '__main__':
    print(findClosestElements([1,2,3,4,5], 4, 3))  # Output: [1,2,3,4]

Line Notes

low, high = 0, len(arr) - kInitialize binary search boundaries for window start

while low < highBinary search loop to narrow down left boundary

if x - arr[mid] > arr[mid + k] - xCompare distances to decide which side to move

return arr[low:low + k]Return the k closest elements starting at low

import java.util.*;

public class Solution {
    public static List<Integer> findClosestElements(int[] arr, int k, int x) {
        int low = 0, high = arr.length - k;
        while (low < high) {
            int mid = (low + high) / 2;
            if (x - arr[mid] > arr[mid + k] - x) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        List<Integer> result = new ArrayList<>();
        for (int i = low; i < low + k; i++) {
            result.add(arr[i]);
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(findClosestElements(new int[]{1,2,3,4,5}, 4, 3)); // [1, 2, 3, 4]
    }
}

Line Notes

int low = 0, high = arr.length - k;Set binary search range for window start

while (low < high)Loop until search space is narrowed

if (x - arr[mid] > arr[mid + k] - x)Decide which half to discard based on closeness

for (int i = low; i < low + k; i++)Collect k closest elements after binary search

#include <iostream>
#include <vector>
using namespace std;

vector<int> findClosestElements(vector<int>& arr, int k, int x) {
    int low = 0, high = arr.size() - k;
    while (low < high) {
        int mid = (low + high) / 2;
        if (x - arr[mid] > arr[mid + k] - x) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return vector<int>(arr.begin() + low, arr.begin() + low + k);
}

int main() {
    vector<int> arr = {1,2,3,4,5};
    vector<int> res = findClosestElements(arr, 4, 3);
    for (int num : res) cout << num << ' ';
    cout << endl;
    return 0;
}

Line Notes

int low = 0, high = arr.size() - k;Initialize binary search boundaries for window start

while (low < high)Binary search loop to find left boundary

if (x - arr[mid] > arr[mid + k] - x)Compare distances to decide direction

return vector<int>(arr.begin() + low, arr.begin() + low + k);Return the k closest elements

function findClosestElements(arr, k, x) {
    let low = 0, high = arr.length - k;
    while (low < high) {
        let mid = Math.floor((low + high) / 2);
        if (x - arr[mid] > arr[mid + k] - x) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return arr.slice(low, low + k);
}

// Test
console.log(findClosestElements([1,2,3,4,5], 4, 3)); // [1,2,3,4]

Line Notes

let low = 0, high = arr.length - k;Set binary search range for window start

while (low < high)Loop to narrow down left boundary

if (x - arr[mid] > arr[mid + k] - x)Compare distances to decide which side to move

return arr.slice(low, low + k);Return the k closest elements after binary search

⏱

Complexity

TimeO(log(n-k) + k)

SpaceO(k)

Binary search takes O(log(n-k)) to find the window start, then O(k) to collect results.

💡 For n=1000 and k=10, this means about 10 steps of binary search plus 10 elements to output, very efficient.

Interview Verdict: Accepted and optimal

This is the best approach to implement in interviews for efficiency and clarity.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, coding the binary search approach is best. The brute force is useful to explain understanding, and the two pointer method is a good intermediate step.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n*k)	O(k)	No	N/A	Mention only - never code
2. Two Pointer Sliding Window	O(n)	O(k)	No	N/A	Good to mention and understand
3. Binary Search on Left Boundary	O(log(n-k) + k)	O(k)	No	N/A	Code this approach in 95% of interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach to show understanding. Progress to better and optimal solutions, and practice coding the binary search approach.

How to Present

Clarify the problem and constraints with the interviewer.Describe the brute force approach and its inefficiency.Explain the two pointer sliding window method as an improvement.Present the binary search on the left boundary as the optimal solution.Code the binary search solution carefully and test with examples.

Time Allocation

Clarify: 3min → Approach discussion: 5min → Coding: 10min → Testing & optimization: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your understanding of binary search beyond exact element search, your ability to find boundaries, and your skill in optimizing from brute force to logarithmic time.

Common Follow-ups

• What if the array is not sorted? → You must sort first or use a different approach.
• How to handle duplicates? → The binary search approach still works as it relies on distances.

💡 These follow-ups test your adaptability and understanding of assumptions in the problem.

🔍

Pattern Recognition

When to Use

1) Array is sorted, 2) Need to find closest elements or a window, 3) Problem involves distance or difference comparisons, 4) Output is a contiguous subarray.

Signature Phrases

k closest elementssorted arraydistance to xwindow of size k

NOT This Pattern When

Problems that require searching for a single element or use two pointers without binary search are different patterns.

Similar Problems

Find First and Last Position of Element in Sorted Array - also uses binary search for boundariesMedian of Two Sorted Arrays - binary search on partition boundariesSearch in Rotated Sorted Array - modified binary search for element location

Practice

1. Consider the following recursive binary search code for finding the insert position of target = 2 in nums = [1, 3, 5, 6]. What is the final returned value?

easy

A. 0

B. 1

C. 2

D. 3

Solution

1. Step 1: Trace binary_search(0, 3)

   mid = (0+3)//2 = 1, nums[1] = 3 > 2, recurse left: binary_search(0, 0)

2. Step 2: Trace binary_search(0, 0)

   mid = (0+0)//2 = 0, nums[0] = 1 < 2, recurse right: binary_search(1, 0)

3. Step 3: Base case binary_search(1, 0)

   left > right, return left = 1 as insertion index

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Target 2 fits between 1 and 3 at index 1 [OK]

Hint: Follow recursive calls and base case carefully [OK]

Common Mistakes:

• Returning right instead of left at base case
• Off-by-one in mid calculation
• Confusing left and right updates

2. What is the time complexity of counting occurrences of a target in a sorted array using binary search to find left and right boundaries?

medium

A. O(n) because you must scan the array to count

B. O(log n) because binary search halves the search space each step

C. O(log n * log n) because two binary searches are performed

D. O(1) because built-in functions are optimized

Solution

1. Step 1: Analyze binary search calls

   Two binary searches are performed independently, each O(log n).

2. Step 2: Combine complexities

   Total time is O(log n) + O(log n) = O(log n), since constants are ignored.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two binary searches do not multiply complexities [OK]

Hint: Two O(log n) calls sum to O(log n) [OK]

Common Mistakes:

• Confusing two calls as O(log n * log n)
• Assuming linear scan is needed
• Believing built-in functions run in O(1)

3. The following code attempts to find the minimum in a rotated sorted array with duplicates. Identify the bug:

def find_min(nums):
    low, high = 0, len(nums) - 1
    while low < high:
        if nums[low] < nums[high]:
            return nums[low]
        mid = (low + high) / 2  # line 6
        if nums[mid] > nums[high]:
            low = mid + 1
        elif nums[mid] < nums[high]:
            high = mid
        else:
            high -= 1
    return nums[low]

What is the bug?

medium

A. Line 6 uses floating point division instead of integer division for mid calculation.

B. The condition nums[low] < nums[high] should be nums[low] <= nums[high].

C. The decrement of high in the else block should be increment of low instead.

D. Returning nums[low] at the end should be returning nums[mid].

Solution

1. Step 1: Examine mid calculation

   Line 6 uses (low + high) / 2 which results in a float in Python 3, causing an error when used as an index.

2. Step 2: Impact of bug

   Using float index causes runtime error or unexpected behavior; integer division (//) is required.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mid must be integer index [OK]

Hint: Mid index must be integer, not float [OK]

Common Mistakes:

• Using / instead of // for mid
• Returning nums[mid] instead of nums[low]

4. What is the time complexity of the optimal binary search algorithm that finds the single non-duplicate element in a sorted array where every other element appears twice?

medium

A. O(n) because each element is checked at least once

B. O(log n) because the search space halves each iteration based on parity checks

C. O(n log n) due to repeated comparisons and index parity calculations

D. O(1) since only a few elements are compared at each step

Solution

1. Step 1: Identify loop behavior

   The while loop halves the search space each iteration by adjusting low or high based on parity comparisons.

2. Step 2: Confirm complexity

   Halving search space each iteration leads to O(log n) time complexity.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Binary search is classic O(log n) [OK]

Hint: Halving search space -> logarithmic time [OK]

Common Mistakes:

• Confusing linear scan with binary search
• Assuming parity checks add extra complexity
• Misreading O(1) as possible for search

5. Suppose the problem is modified so that the array is sorted but the single element can appear multiple times (not necessarily once), and all other elements appear exactly twice. Which modification to the binary search approach correctly finds the single element?

hard

A. Modify binary search to compare mid with neighbors and adjust search space based on counts of duplicates around mid

B. Switch to linear scan because binary search parity logic breaks when single element repeats

C. Use the same parity-based binary search since duplicates still appear in pairs

D. Use a hash map to count occurrences since binary search can't handle multiple single elements

Solution

1. Step 1: Understand problem change

   The single element may appear multiple times, breaking the strict pair pattern.

2. Step 2: Analyze binary search adaptation

   Parity-based halving fails; instead, compare mid with neighbors and count duplicates to decide which half to search.

3. Step 3: Confirm other options

   Linear scan is inefficient; hash map uses extra space and is unnecessary if modified binary search works.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Counting duplicates around mid guides correct binary search [OK]

Hint: Modify binary search to handle variable duplicate counts [OK]

Common Mistakes:

• Assuming parity logic still works
• Switching to linear scan prematurely
• Using extra space unnecessarily