diff options
Diffstat (limited to 'first_last_sorted_array.cpp')
-rw-r--r-- | first_last_sorted_array.cpp | 47 |
1 files changed, 47 insertions, 0 deletions
diff --git a/first_last_sorted_array.cpp b/first_last_sorted_array.cpp new file mode 100644 index 0000000..3f4168a --- /dev/null +++ b/first_last_sorted_array.cpp @@ -0,0 +1,47 @@ +#include "leetcode.h" + +class Solution { +public: + vector<int> searchRange(vector<int> &nums, int target) { + int s = 0, e = nums.size() - 1; + vector<int> ans(2, -1); + // first position + while (s <= e) { + int m = s + (e - s) / 2; + if (nums[m] < target) + s = m + 1; + else if (nums[m] > target) + e = m - 1; + else { + if (m == s || nums[m] != nums[m - 1]) { + ans[0] = m; + break; + } else { + e = m - 1; + ans[0] = m - 1; + } + } + } + // second position + s = 0, e = nums.size() - 1; + while (s <= e) { + int m = s + (e - s) / 2; + if (nums[m] < target) + s = m + 1; + else if (nums[m] > target) + e = m - 1; + else { + if (m == e || nums[m] != nums[m + 1]) { + ans[1] = m; + break; + } else { + s = m + 1; + ans[1] = m + 1; + } + } + } + return ans; + } +}; + +int main() {} |