如何通过二分查找统计已排序数组中重复元素的索引值？

当然可以用二分查找来实现这个需求！我来帮你梳理问题，找到之前代码的问题所在，再给出可行的解决方案。

核心思路 #

已排序数组里的重复元素是连续排列的，所以要统计所有重复元素的索引，关键是先通过二分查找找到目标元素第一次出现的左边界和最后一次出现的右边界，然后把这两个边界之间的所有索引收集起来就行。你之前的代码应该是只找到了某一个匹配的中间索引，没有去拓展寻找左右边界，所以才会始终输出相同的索引值。

完整实现代码（C#） #

下面是针对这个需求的完整代码示例，包含左边界、右边界查找，以及索引收集的逻辑：

using System;
using System.Collections.Generic;

class BinarySearchDuplicates
{
    // 查找目标元素的第一个出现位置（左边界）
    private static int FindLeftBoundary(int[] arr, int target)
    {
        int left = 0;
        int right = arr.Length - 1;
        int result = -1;
        
        while (left <= right)
        {
            int mid = left + (right - left) / 2; // 避免溢出的写法
            if (arr[mid] == target)
            {
                result = mid;
                right = mid - 1; // 找到匹配后继续向左搜索，确保找到第一个出现的位置
            }
            else if (arr[mid] < target)
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }
        return result;
    }

    // 查找目标元素的最后一个出现位置（右边界）
    private static int FindRightBoundary(int[] arr, int target)
    {
        int left = 0;
        int right = arr.Length - 1;
        int result = -1;
        
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target)
            {
                result = mid;
                left = mid + 1; // 找到匹配后继续向右搜索，确保找到最后一个出现的位置
            }
            else if (arr[mid] < target)
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }
        return result;
    }

    // 收集目标元素的所有重复索引
    public static List<int> GetAllDuplicateIndices(int[] sortedArr, int target)
    {
        List<int> duplicateIndices = new List<int>();
        int leftBoundary = FindLeftBoundary(sortedArr, target);
        
        if (leftBoundary == -1) // 目标元素不存在于数组中
        {
            return duplicateIndices;
        }
        
        int rightBoundary = FindRightBoundary(sortedArr, target);
        
        // 遍历左边界到右边界的所有索引，加入结果列表
        for (int i = leftBoundary; i <= rightBoundary; i++)
        {
            duplicateIndices.Add(i);
        }
        
        return duplicateIndices;
    }

    // 测试示例
    static void Main(string[] args)
    {
        int[] testArray = {1, 2, 2, 2, 3, 4, 4, 5};
        int targetNum = 2;
        List<int> result = GetAllDuplicateIndices(testArray, targetNum);
        
        Console.WriteLine("目标元素的所有重复索引：");
        foreach (int idx in result)
        {
            Console.WriteLine(idx);
        }
        // 输出结果：1、2、3
    }
}

关键细节解释 #

• 左边界查找：当找到匹配的元素时，不直接返回索引，而是将右指针左移，继续搜索左侧区域，直到确定这是第一个出现的位置。
• 右边界查找：同理，找到匹配元素后将左指针右移，继续搜索右侧区域，确定最后一个出现的位置。
• 索引收集：得到左右边界后，遍历两个边界之间的所有索引，就能得到该元素的全部重复位置了。

这样修改后，你就能正确统计已排序数组中重复元素的所有索引啦！

内容的提问来源于stack exchange，提问作者user9090260