二分查找應用 --- 有序數組中的單一元素
前言
大家好，我是程序員小熊，來自大廠的程序猿。瞭解二分查找的童鞋，都知道二分查找常用於在有序數組中查找某一特定元素，而且很多童鞋也都知道二分查找的模板該怎麼寫。
今天小熊帶來一道亞馬遜的面試題，也就是力扣 540. 有序數組中的單一元素，這道題難度爲中等，採用 “二分查找 + 動圖” 的方式深入剖析，供大家參考，希望對大家有所幫助。
題目
給定一個只包含整數的有序數組，每個元素都會出現兩次，唯有一個數只會出現一次，找出這個數。
示例 1:
輸入: [1,1,2,3,3,4,4,8,8]
輸出: 2
示例 2:
輸入: [3,3,7,7,10,11,11]
輸出: 10
注意: 您的方案應該在 O(log n)時間複雜度
和 O(1)空間複雜度中運行。解題思路
本題如果不要求解法的時間複雜度爲 O(log n) 的話，就跟力扣 136. 只出現一次的數字差不多，只是後者不要求數組是有序的，但解法一樣，可以通過異或去做，因爲一個數字跟自身相異或，結果爲 0；但異或 0，結果爲自身，因此讓數組中所有元素都相互異或即可得到結果，但時間複雜度爲 O(n)。
由於題目明確要求解法的時間複雜度爲 O(log n)，對二分查找有所瞭解的童鞋，很自然地會想到需要採用二分查找法去做。
那具體如何通過二分查找去做呢？見下面例子。
舉例
以數組 [3,3,7,7,10,11,11] 爲例子，如下圖示。
示例
二分查找一般通過數組的中間元素 nums[mid] 判斷 target 的位置（在 mid 位置，亦或是在 mid 的左側或右側），本題也不例外。
確定中間元素
由題意可知，數組長度一定爲奇數，因此可以進行如下操作：
-
1、判斷中間元素是否跟兩側元素相等；
-
2、若等於任意一側元素，則去掉中間元素及其跟它相等的元素，將原數組分爲兩部分（奇數長度和偶數長度），由於唯一的那個數一定存在於奇數長度的數組，因此丟棄偶數長度的子數組，在奇數長度的子數組中重複 1 和 2；
-
3、若不等於兩側元素，則中間元素就是要查找的只出現一次的那個數字。
如下圖示：
1、判斷 nums[mid] == nums[mid - 1]；
2、移除 nums[mid] 和 nums[mid - 1]；
3、判斷拆分後的兩數組的長度，並移除偶數長度子數組；
4、在奇數長度的子數組中重複前 1、2、3 步；
查找過程完整動態展示
動態如下：
Show me the Code
C
int singleNonDuplicate(int* nums, int numsSize){
int left = 0, right = numsSize - 1;
while (left < right) {
int mid = left + ((right - left) >> 1);
/* 判斷（子）數組的長度，進而確認 target 位置 */
bool halvesAreEven = (right - mid) % 2 == 0;
/* 中間元素等於右邊元素 */
if (nums[mid + 1] == nums[mid]) {
/* halvesAreEven 爲偶數，mid 右側存在 target */
if (halvesAreEven) {
left = mid + 2;
/* halvesAreEven 爲奇數，mid 左側存在 target */
} else {
right = mid - 1;
}
/* 中間元素等於左側元素 */
} else if (nums[mid - 1] == nums[mid]) {
/* halvesAreEven 爲偶數，mid 左側存在 target */
if (halvesAreEven) {
right = mid - 2;
/* halvesAreEven 爲奇數，mid 右側存在 target */
} else {
left = mid + 1;
}
/* 中間元素跟左右側元素都不等，中間元素是target */
} else {
return nums[mid];
}
}
return nums[left];
}簡化
上面的代碼略顯冗餘，if 跟 else if 中均需要先判斷 nums[mid] 與兩側的元素是否相等，再判斷 halvesAreEven 是否爲奇數，然後決定在 mid 的左側還是右側查找，有沒有簡便一點的方法？
答案是有的。
-
1、將 nums[mid + 1]、nums[mid - 1] 與 nums[mid] 比較，簡化爲 nums[temp] 與 nums[mid] 比較，其中 temp = mid ^ 1，若相等則左邊界 left 右移（left = mid + 1）繼續查找；
-
2、若不相等，則相當於 nums[mid] 與左右兩側元素都不相等，相當於 mid 就是待查找的只出現一次的那個數字。
舉例
以數組 [1,1,2,3,3,4,4] 爲例子，如下動圖示。
示例動圖
Show me the Code
C++
int singleNonDuplicate(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
int temp = mid ^ 1;
if (nums[mid] == nums[temp]) {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left];
}Golang
func singleNonDuplicate(nums []int) int {
left, right := 0, len(nums) - 1
for left < right {
mid := left + (right - left) / 2;
temp := mid ^ 1;
if nums[mid] == nums[temp] {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left]
}Python3
def singleNonDuplicate(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = (right + left) // 2;
temp = mid ^ 1;
if nums[mid] == nums[temp]:
left = mid + 1
else:
right = mid
return nums[left]複雜度分析
空間複雜度：O(1)，未開闢額外存儲空間。
時間複雜度：O(logn)，n 爲數組長度。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/w-6W9z7Ura7dayMzR0LEVg