LeetCode第540题：有序数组中的单一元素

题干

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

示例 1:

输入: [1,1,2,3,3,4,4,8,8]
输出: 2
复制代码

示例 2:

输入: [3,3,7,7,10,11,11]
输出: 10
复制代码

思路1：一次循环

这种解法思路比较简单，每一次循环时将当前元素与下一个元素进行比较，如果相同，则继续，直至循环结束，返回最后一个元素；不同则返回当前值。

执行用时：80 ms, 在所有 JavaScript 提交中击败了83.39%的用户

内存消耗：38.6 MB, 在所有 JavaScript 提交中击败了100.00%的用户

 var singleNonDuplicate = function (nums) {
    let length = nums.length;
    if (length == 1) {
      return nums[0]
    }
    for (let i = 0; i < length - 1;) {
      if (nums[i] == nums[i + 1]) {
        i = i + 2;
      } else {
        return nums[i]
      }
    }
    return nums[length - 1]
  };
复制代码

思路2：二分法

这道题依然可以使用二分法来解决，就是按照我们的位置进行判断，如果我们当前的位置时偶位置，那么根据与左右元素的对比情况来判断二分的边界，奇位置与偶位置判定相反。

画图分析一下：

代码实现：

 /**
 * @param {number[]} nums
 * @return {number}
 */
var singleNonDuplicate2 = function (nums) {
    // 二分思想
    let mid = 0;
    let min = 0;
    let max = nums.length - 1;
    while (min <= max) {
        mid = Math.floor((min + max) / 2);
        let right = nums[mid + 1];
        let left = nums[mid - 1];
        if (right != nums[mid] && left != nums[mid]) { return nums[mid] }
        if (mid % 2 == 0) {
            if(nums[mid]==right){
                min=mid+1
            }else{
                max=mid-1
            }
        } else {
            if(nums[mid]==left){
                min=mid+1
            }else{
                max=mid-1
            }
        }
    }
};
复制代码