1536 · Find First and Last Position of Element in Sorted Array - LintCode

# Description

Given an array of integers nums 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] .

# Example

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

use binary search 2 times

	public class Solution {
	/**
	* @param nums: the array of integers
	* @param target:
	* @return: the starting and ending position
	*/
	public List<Integer> searchRange(List<Integer> nums, int target) {
	List<Integer> result = new ArrayList<>();
	if (nums == null \|\| nums.size() == 0){
	return Arrays.asList(-1, -1);
	}
	int firstpos = search(nums, target, true);
	int lastpos = search(nums, target, false);
	result.add(firstpos);
	result.add(lastpos);
	return result;
	}
	private int search(List<Integer> nums, int target, boolean isFirst){
	int start = 0, end = nums.size() - 1;
	while (start + 1 < end){
	int mid = start + (end - start) / 2;
	if (nums.get(mid) == target) {
	if (isFirst){
	end = mid;
	} else {
	start = mid;
	}
	} else if (nums.get(mid) < target) {
	start = mid;
	} else {
	end = mid;
	}
	}

	if(isFirst){
	if (nums.get(start) == target){
	return start;
	}
	if (nums.get(end) == target){
	return end;
	}
	} else {
	if (nums.get(end) == target){
	return end;
	}
	if (nums.get(start) == target){
	return start;
	}
	}

	return -1;
	}
	}