Leetcode 540. 有序数组中的单一元素（DAY 181）---- 二分查找学习期

刺骨的言语ヽ痛彻心扉 2022-09-14 09:05 174阅读 0赞

### 文章目录 ###

*   *  原题题目
     *  代码实现（首刷自解 二分查找）

--------------------

## 原题题目 ##

--------------------

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]

--------------------

## 代码实现（首刷自解 二分查找） ##

--------------------

class Solution { 
    public:
        int my_lower_bound(vector<int>& nums,int target)
        { 
            int left = 0,right = nums.size();
            while(left < right)
            { 
                int mid = (left + right)/2;
                if(nums[mid] < target)  left = mid+1;
                else  right = mid;
            }
            return left;
        }
    
        int singleNonDuplicate(vector<int>& nums) 
        { 
            int ret = 0,left = 0,right = nums.size()-1;
            while(left < right)
            { 
                int pos = my_lower_bound(nums,nums[(left+right)/2]);
                int size = (pos - left);
                if(!(size % 2)) 
                { 
                    if(left == pos) left += 2;
                    else    left = pos;
                }
                else    right = pos - 1;
            }
            return nums[left];
        }
    };

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/4d0fc1a9e39d409e81602311f1ca81d8.png