Line data    Source code

       1              : // Copyright (c) 2024 The Authors. All rights reserved.
       2              : //
       3              : // Licensed under the Apache License, Version 2.0 (the "License");
       4              : // you may not use this file except in compliance with the License.
       5              : // You may obtain a copy of the License at
       6              : //
       7              : //      https://www.apache.org/licenses/LICENSE-2.0
       8              : //
       9              : // Unless required by applicable law or agreed to in writing, software
      10              : // distributed under the License is distributed on an "AS IS" BASIS,
      11              : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
      12              : // See the License for the specific language governing permissions and
      13              : // limitations under the License.
      14              : 
      15              : // Authors: liubang (it.liubang@gmail.com)
      16              : 
      17              : #include <gtest/gtest.h>
      18              : 
      19              : #include <vector>
      20              : 
      21              : namespace {
      22              : class Solution {
      23              : public:
      24            2 :     int findMin(const std::vector<int>& nums) {
      25            2 :         int s = 0, e = nums.size() - 1;
      26            6 :         while (s < e) {
      27            4 :             int m = (s + e) / 2;
      28            4 :             if (nums[m] > nums[e]) {
      29            1 :                 s = m + 1;
      30            3 :             } else if (nums[m] < nums[e]) {
      31            3 :                 e = m;
      32              :             } else {
      33            0 :                 e--;
      34              :             }
      35              :         }
      36            2 :         return nums[s];
      37              :     }
      38              : };
      39              : } // namespace
      40              : 
      41            4 : TEST(Leetcode, find_minimum_in_rotated_sorted_array_ii) {
      42            1 :     Solution s;
      43            1 :     EXPECT_EQ(1, s.findMin({1, 3, 5}));
      44            1 :     EXPECT_EQ(0, s.findMin({2, 2, 2, 0, 1}));
      45            1 : }