LeetCode 540.有序数组中的单一元素

思路一：hash，键存入元素，值存入次数，然后遍历，不是最优解

思路二：二分查找

• 假设数组为 [1, 1, 2, 2, 3, 4, 4]，其中唯一出现一次的元素是 3。
• 在一个有序数组中，如果没有唯一的元素，那么对于每一对数字，成对元素的第一个数字一定出现在偶数索引上，第二个数字出现在奇数索引上。例如，1 的第一个出现位置在索引 0，第二个位置在索引 1；2 的第一个位置在 2，第二个位置在 3，依此类推
• 当 mid 是偶数时，我们可以比较 nums[mid] 和 nums[mid + 1]，如果它们相等，说明到 mid 为止都是成对出现的，因此唯一的元素在右半部分。
• 如果 nums[mid] 和 nums[mid + 1] 不相等，说明唯一的元素在左半部分，因为唯一的元素打破了成对出现的规律。
• 在代码中，通过 if (mid % 2 == 1) mid--; 确保 mid 是偶数索引。如果 mid 是奇数，就将其减 1，使其变为偶数索引。
• 这样我们可以始终确保 mid 是偶数索引，便于进行对比 nums[mid] 和 nums[mid + 1]，从而更有效地缩小查找范围。