Leetcode 34. Search for a Range

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 ofO(logn).

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].

题目简述：

给定一个升序排列的int 数组，找到给定数值的起始和终止位置。

时间复杂度要求 O（logn）

复杂度要求logn 首先考虑的就是binary search。

复杂度为O（N2）的思路很简单，计算nums[i] == target 的个数，主要考虑一下找不到的情况，然后将数组赋值为[ -1, -1 ]。

JAVA 版本：

public int[] searchRange(int[] A, int target) {
  if (A.length == 0) {
return new int[]{-1, -1};
}
int start, end, mid;
int[] bound = new int[2];

// search for left bound

start = 0;
end = A.length - 1;
  while (start + 1 < end) {
    mid = start + (end - start) / 2;
    if (A[mid] >= target) {
      end = mid;
    } else {
      start = mid;
    }
  }
    if (A[start] == target) {
         bound[0] = start;
    } else if (A[end] == target) {
      bound[0] = end;
    } else {
      bound[0] = bound[1] = -1;
      return bound;
}

  // search for right bound

  start = 0;
  end = A.length - 1;
  while (start + 1 < end) {
    mid = start + (end - start) / 2;
    if (A[mid] <= target) {
      start = mid;
    } else {
      end = mid;
    }
  }
  if (A[end] == target) {
    bound[1] = end;
  } else if (A[start] == target) {
    bound[1] = start;
  } else {
    bound[0] = bound[1] = -1;
    return bound;
  }
  return bound;
}