如何理解该算法利用二分搜索统计有序数组唯一整数的逻辑？

这段代码的核心思路是利用有序数组中相同元素连续排列的特性，通过二分搜索快速定位当前元素的最后出现位置，从而跳过所有重复项，高效统计唯一元素数量。

整体逻辑（unique函数） #

1. 初始化指针i为数组起始位置，计数器count为0。
2. 循环中，每次调用nextIndex找到当前元素a[i]的下一个不同元素的起始索引，将i更新到该位置。
3. 每完成一次跳转，计数器count加1，直到i超出数组范围，此时count就是唯一元素的总数。

核心：nextIndex的二分搜索逻辑 #

这个函数的作用是找到当前目标元素target最后一次出现的位置，并返回该位置的下一个索引，具体步骤：

• 参数l是当前元素的起始搜索位置，r初始化为数组末尾索引。
• 二分搜索循环：
  • 计算中间位置mid（用l + (r-l)/2避免整数溢出）。
  • 如果a[mid] == target：说明当前mid位置是target，且右侧可能还有相同元素，因此将左指针l移到mid + 1，继续向右搜索。
  • 如果a[mid] != target：因为数组有序，说明mid位置的元素大于target（左侧都是<=target的），因此将右指针r移到mid - 1，缩小搜索范围到左侧。
• 循环结束时，r会指向最后一个等于target的元素的索引，返回r + 1就是下一个不同元素的起始位置。

示例演示 #

假设数组为[1,1,2,3,3,3,4]：

1. 初始i=0，target=1：
   • 二分搜索最后一个1的位置是1，返回1+1=2，count变为1，i更新为2。
2. i=2，target=2：
   • 二分搜索最后一个2的位置是2，返回2+1=3，count变为2，i更新为3。
3. i=3，target=3：
   • 二分搜索最后一个3的位置是5，返回5+1=6，count变为3，i更新为6。
4. i=6，target=4：
   • 二分搜索最后一个4的位置是6，返回6+1=7，count变为4，此时i=7等于数组长度，循环结束。
     最终返回4，与数组中唯一元素{1,2,3,4}的数量一致。

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