查找排序数组中的单个元素，其中每个元素出现两次，除了一个 |数据结构与算法

Question

我正在尝试理解此 link 中给出的此问题的解决方案。它在 O(logN) 时间内解决了问题。

// A Binary Search based function to find the element 
// that appears only once 
void search(int *arr, int low, int high) 
{ 
     // Base cases 
    if (low > high) 
       return; 

    if (low==high) 
    { 
        printf("The required element is %d ", arr[low]); 
        return; 
    } 

    // Find the middle point 
    int mid = (low + high) / 2; 

    // If mid is even and element next to mid is 
    // same as mid, then output element lies on 
    // right side, else on left side 
    if (mid%2 == 0) 
    { 
        if (arr[mid] == arr[mid+1]) 
            search(arr, mid+2, high); 
        else
            search(arr, low, mid); 
    } 
    else  // If mid is odd 
    { 
        if (arr[mid] == arr[mid-1]) 
            search(arr, mid+1, high); 
        else
            search(arr, low, mid-1); 
    } 
}

我能理解这个方法。但我不明白为什么当 mid 是偶数且 arr[mid] != arr[mid + 1]。为什么我们做 high = mid 而不是 high = mid - 1。我找到了将它带到无限循环的测试用例。但是，我无法理解为什么我们再次包含 mid 的充分理由，即使我们用 mid + 1

检查了上面的情况

如果有人能解释清楚我们使用 high = mid 的原因，那将非常有帮助而不是 high = mid - 1.

这是进入无限循环的测试用例。

[1,1,2,3,3,4,4,8,8]

Answer 1

当mid is even and arr[mid] != arr[mid + 1]时，唯一值可以是mid本身。所以你必须从 [low, mid] 重新运行搜索。例如，考虑这个数组

[1,1,2,3,3]

在第一遍中，mid是偶数，arr[mid] != arr[mid + 1]。但是如果你只在[low, mid-1]上运行search，你将永远找不到唯一的数字，因为这个数字本身就是mid。

查找排序数组中的单个元素，其中每个元素出现两次，除了一个 |数据结构与算法

FInd the Single Element in a sorted array where every element occurs twice except one | Data Structures & Algorithms

algorithm

binary-search

data-structures