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

Question

我正在尝试了解此链接中给出的此问题的解决方案。 它在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的。