Thursday, January 22, 2015

LeetCode Search for a range

Find the first element
Find the second element

Find values from sorted array with duplicate elements;
public int[] searchRange(int[] A, int target) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int[] result = new int[2];
        result[0] = findFirstElement(A, 0, A.length-1, target);
        result[1] = findSecondElement(A, 0, A.length-1, target);
        return result;
}

private int findFirstElement(int[] array, int low, int high, int target) {
   while (low <= high) {
       int mid = (low + high)/2;
       if (mid==low && array[mid] == target || array[mid]== target && array[mid-1] < array[mid]) {
           return mid;
       } else {
           if (array[mid] >= target) {
               high = mid - 1;
           } else {
               low = mid + 1;
           }
       }
   }
   return -1;
}

private int findSecondElement(int[] array, int low, int high, int target) {
   while (low <= high) {
       int mid = (low + high)/2;
       if (mid == high && array[mid] == target || array[mid]==target && array[mid] < array[mid+1]) {
           return mid;
       } else {
           if (array[mid] <= target) {
               low = mid + 1;
           } else {
               high = mid - 1;
           }
       }
   }
   return -1;
}

No comments:

Post a Comment