My 4ms C solution with explanation


  • 0
    Z

    Algorithm is broken down into 3 steps.

    1. do a binary search across the entire array to find the pivot (anyone == target, regardless if more of the same exists towards its left or right)

    2. push the left boundary of the range by bin-search([0, pivot -1])]. if still find one, repeat toward the leftmost

    3. vice verse for the right boundary bin-search([pivot+1, numsSize-1]);

      int bSearch(int* nums, int l, int r, int t)
      {
      // your own binary search implementation here
      }

      int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
      returnSize = 2;
      int
      res = (int*)malloc(sizeof(int)* *returnSize);
      int pvt = bSearch(nums, 0, numsSize -1, target);
      if(pvt == -1)
      {
      res[0] = res[1] = -1;
      return res;
      }

      // then b-search towards left and right until -1
      res[0] = res[1] = pvt;
      int temp = pvt -1;
      while((temp = bSearch(nums, 0, temp, target)) > -1)
      res[0] = temp--;

      temp = pvt+1;
      while((temp = bSearch(nums, temp, numsSize-1, target)) > -1)
      res[1] = temp++;

      return res;
      }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.