Beats 100% Java Solutions
Code Explanation\n\njava\npublic int singleNonDuplicate(int[] nums) {\n    int low = 0;\n    int high = nums.length - 1;\n\n    while (low < high) {\n        in
## Code Explanation\n\n```java\npublic int singleNonDuplicate(int[] nums) {\n    int low = 0;\n    int high = nums.length - 1;\n\n    while (low < high) {\n        int mid = low + (high - low) / 2;\n        if (mid % 2 == 1) {\n            mid--;\n        }\n\n        if (nums[mid] == nums[mid + 1]) {\n            low = mid + 2;\n        } else {\n            high = mid;\n        }\n    }\n    return nums[low];\n}\n```\n\n#### Detailed Breakdown:\n\n1. **Initialization**:\n    ```java\n    int low = 0;\n    int high = nums.length - 1;\n    ```\n    - `low` and `high` are initialized to the start and end of the array, respectively.\n\n2. **Binary Search Loop**:\n    ```java\n    while (low < high) {\n    ```\n    - This loop continues until `low` is equal to `high`.\n\n3. **Finding the Middle Element**:\n    ```java\n    int mid = low + (high - low) / 2;\n    if (mid % 2 == 1) {\n        mid--;\n    }\n    ```\n    - `mid` is calculated to be the middle index between `low` and `high`.\n    - If `mid` is odd, it is decremented by 1 to make it even. This ensures that we are always comparing pairs starting with an even index.\n\n4. **Comparison**:\n    ```java\n    if (nums[mid] == nums[mid + 1]) {\n        low = mid + 2;\n    } else {\n        high = mid;\n    }\n    ```\n    - If the element at `mid` is equal to the element at `mid + 1`, it means that the single non-duplicate element is in the right half of the array. So, `low` is updated to `mid + 2`.\n    - If `nums[mid]` is not equal to `nums[mid + 1]`, it means the single non-duplicate element is in the left half of the array, including the current `mid`. Hence, `high` is updated to `mid`.\n\n5. **Return Statement**:\n    ```java\n    return nums[low];\n    ```\n    - When `low` equals `high`, the loop exits and the single non-duplicate element is at the index `low`.\n\n### Example Walkthrough:\n\nConsider the array `[1, 1, 2, 3, 3, 4, 4, 5, 5]`:\n- Initial state: `low = 0`, `high = 8`\n- First iteration:\n  - `mid = 4` (even)\n  - `nums[mid]` (3) == `nums[mid + 1]` (3)\n  - Update `low = mid + 2 = 6`\n- Second iteration:\n  - `mid = 7`\n  - `mid` is odd, so adjust to `mid = 6` (even)\n  - `nums[mid]` (4) != `nums[mid + 1]` (5)\n  - Update `high = mid = 6`\n- Third iteration:\n  - `low = 6`, `high = 6`\n  - Exit loop and return `nums[low] = 2`\n\nThis approach ensures O(log n) time complexity due to the binary search mechanism, making it efficient for large arrays.
[]