[leetcode] 34. 정렬 배열 에서 요소 의 첫 번 째 와 마지막 위 치 를 찾 습 니 다 (2 분 찾기)

7558 단어 leetcode
오름차 순 으로 배 열 된 정수 배열 nums 와 목표 값 target 을 지정 합 니 다.주어진 목표 값 이 배열 의 시작 위치 와 끝 위 치 를 찾 습 니 다.
당신 의 알고리즘 시간 복잡 도 는 반드시 O (log n) 등급 이 어야 합 니 다.
배열 에 목표 치가 존재 하지 않 으 면 [- 1, - 1] 을 되 돌려 줍 니 다.
예시 1:
입력: nums = [5, 7, 7, 8, 8, 10], target = 8 출력: [3, 4]
예시 2:
입력: nums = [5, 7, 7, 8, 8, 10], target = 6 출력: [- 1, - 1]
링크:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
사고 2: 2 분 에 찾 아 왼쪽 과 오른쪽 두 개의 경 계 를 찾 습 니 다.코드 참조 리 뷰 영역
// https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
// 34.                      
//            O(log n)   
vector<int> searchRange(vector<int>& nums, int target) {
	int l = 0;
	int r = nums.size() - 1;

	int res = -1;
	while (l <= r)
	{
		int mid = l + (r - l) / 2;
		if (nums[mid] == target)
		{
			res = mid;
			l = mid;
			r = mid;
			break;
		}
		if (nums[mid] < target) l = mid + 1;
		if (nums[mid] > target) r = mid - 1;
	}
	if (res == -1)
	{
		return vector<int>{-1, -1};
	}
	else
	{
		for (int i = res-1; i >= 0; i--)
		{
			if (nums[i] == target)
			{
				l = i;
			}
		}
		for (int i = res + 1; i < nums.size(); i++)
		{
			if (nums[i] == target)
			{
				r = i;
			}
		}
	}

	return vector<int>{l, r};
}

좋은 웹페이지 즐겨찾기