leetcode - 34. Search for a Range - Medium

descrition

Given an array of integers sorted in ascending order, 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].

解析

对于有序数组的查找问题，基本上都可以使用折半查找的思路。再者题目的要求复杂度是 O(log n)，因此我们需要两次折半查找。如果我们只用一次折半查找，找到数组 target 出现的任意一个位置，然后线性遍历找到最左边和最右，需要的复杂度是 O(n)。

具体实现代码如下。

code

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

class Solution{

public:

	vector<int> searchRange(vector<int>& nums, int target) {

		vector<int> ans(2, -1);

		int ileft = binarySearchLeftMost(nums, target);

		if(ileft < 0)

			return ans;

		int iright = binarySearchRightMost(nums, target);

		ans[0] = ileft;

		ans[1] = iright;

		return ans;

	}

	int binarySearchLeftMost(vector<int>& nums, int target){

		int ans = -1; // save the left most index in nums which equal to target

		int ileft = 0, iright = nums.size() - 1;

		while(ileft <= iright){

			int imid = ileft + (iright - ileft) / 2;

			if(nums[imid] == target){

				ans = imid;

				iright = imid - 1;

			}else if (nums[imid] < target){

				ileft = imid + 1;

			}else{

				// nums[imid] > target

				iright = imid - 1;

			}

		}

		return ans;

	}

	int binarySearchRightMost(vector<int>& nums, int target){

		int ans = -1;

		int ileft = 0, iright = nums.size() - 1;

		while(ileft <= iright){

			int imid = ileft + (iright - ileft) / 2;

			if(nums[imid] == target){

				ans = imid;

				ileft = imid + 1;

			}else if (nums[imid] < target){

				ileft = imid + 1;

			}else {

				// nums[imid] > target

				iright = imid - 1;

			}

		}

		return ans;

	}

};

int main()

{

	return 0;

}