34.Find-First-and-Last-Position-of-Element-in-Sorted-Array

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

题目地址

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

http://www.lintcode.com/problem/search-for-a-range/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 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]

代码

Approach #1 Binary Search

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ans = {-1, -1};

        int leftIndex = helper(nums, target, true);

        if (leftIndex == nums.length || nums[leftIndex] != target) {
            return ans;
        }

        ans[0] = leftIndex;
        ans[1] = helper(nums,target, false);

        return ans;
    }

    private int helper(int[] nums, int target, boolean isLeft) {
        int low = 0;
        int high = nums.length - 1;

        while (low + 1 < high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                if (isLeft) {
                    high = mid;
                } else {
                    low = mid;
                }
            } 
            else if (nums[mid] > target) {
                high = mid;
            }
            else {
                low = mid;
            }
        }

        if (isLeft) {
            if (nums[low] == target) {
                return low;
            } else if (nums[high] == target) {
                return high;
            } 
        } else {
            if (nums[high] == target) {
                return high;
            } else if (nums[low] == target) {
                return low;
            }
        }

        return -1;
    }
}

Approach #2

public class Solution {
    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];

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

    if (A[start] == target) {
      bound[0] = start;
    } else if (A[end] == target) {
      bound[0] = end;
    } else {
      bound[0] = bound[1] = -1;
      return bound;
    }

    start = 0;
    end = A.length - 1;
    while (start + 1 < end) {
      mid = start + (end - start) / 2;
      if (A[mid] == target) {
        start = mid; // difference
      } else 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;
  }

}