[LeetCode] 34. Find First and Last Position of Element in Sorted Array

轉自LeetCode

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

<Solution>

看到搜尋，又看到時間要求是 O(logn)

直覺就想到 binary search

但題目是要求 range

最直覺的作法就是 binary search 找到 target，然後再往兩邊找起始和結尾

可是這樣就不是 O(logn) 了，例如 [2,2,2,2,2] 找 2 的時候，往兩邊找的動作就是 O(n)

雖然還是會過，但是不符合題意

查了下資料，可以看這邊的說明

主要想法是

• 先找二分法找左邊界

• 如果沒有左邊界，就直接結束

• 再找右邊界

實作上有幾個細節的部分要注意，可以上面提到的參考資料

code 如下

c++

	class Solution {
	public:
	vector<int> searchRange(vector<int>& nums, int target) {
	vector<int> ans(2,-1);
	//> search left boundary of target
	int left = 0, right = nums.size() - 1;
	while(left < right) { //> don't use left <= right
	int mid = (left + right) / 2;
	if(nums[mid] < target) {
	left = mid + 1;
	}
	else {
	right = mid;
	}
	}
	//> target not in vector
	if(nums[left] != target) {
	return ans;
	}
	else {
	ans[0] = left;
	}
	//> search right boundary of target
	right = nums.size() - 1;
	while(left < right) { //> don't use left <= right
	int mid = (left + right) / 2 + 1; //> notice here, must plus 1 to keep while loop running
	if(nums[mid] > target) {
	right = mid - 1;
	}
	else {
	left = mid;
	}
	}
	ans[1] = right;
	return ans;
	}
	};

view raw searchForARange.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun searchRange(nums: IntArray, target: Int): IntArray {
	var left = 0
	var right = nums.size
	var mid = 0
	//find first
	while(left < right) {
	mid = left + (right - left) / 2
	if(nums[mid] < target) {
	left = mid + 1
	} else {
	right = mid
	}
	}
	val firstPos = if(right == nums.size || nums[right] != target) {
	return intArrayOf(-1, -1)
	} else {
	right
	}
	//>> find last
	right = nums.size
	while(left < right) {
	mid = left + (right - left) / 2
	if(nums[mid] <= target) {
	left = mid + 1
	} else {
	right = mid
	}
	}
	val lastPos = right - 1 //>> right point to the first one bigger than target
	return intArrayOf(firstPos, lastPos)
	}
	}

view raw find_first_and_last_position_of_element_in_sorted_array.kt hosted with ❤ by GitHub