aboutsummaryrefslogtreecommitdiff
path: root/find_first_last_array.c
blob: a7d546837faa9e653641fb9cb6d07bc6d9ff793a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// 34. Find First and Last Position of Element in Sorted Array
#include <stdio.h>
#include <stdlib.h>

/*
 * given an array of integers 'nums' sorted in non-decreasing order, find the
 * starting ending position of a given 'target' value. if target is not found in
 * the array, return '[-1, -1]'. you must write an algorithm with O(log n)
 * runtime complexity
 */

int *searchRange(int *nums, int nums_size, int target, int *return_size) {
  int l = 0, r = nums_size - 1, mid = r / 2;
  *return_size = 2;
  int *ans = malloc(sizeof(int) * 2);
  ans[0] = -1;
  ans[1] = -1;
  while (l <= r) {
    mid = l + (r - l) / 2;
    if (target == nums[mid]) {
      int mid2 = mid;
      while (l < mid) {
        int l_mid = (mid + l) / 2;
        if (nums[l_mid] < target)
          l = l_mid + 1;
        else
          mid = l_mid;
      }
      while (mid2 < r) {
        int r_mid = (mid2 + r + 1) / 2;
        if (nums[r_mid] > target)
          r = r_mid - 1;
        else
          mid2 = r_mid;
      }
      ans[0] = l;
      ans[1] = r;
      return ans;
    } else if (target < nums[mid])
      r = mid - 1;
    else if (target > nums[mid])
      l = mid + 1;
  }
  return ans;
}

int main() {
  int n1[] = {5, 7, 7, 8, 8, 10}, n2[] = {5, 7, 7, 8, 8, 10}, n3[] = {};
  int *sr1 = searchRange(n1, 6, 8, NULL);
  int *sr2 = searchRange(n2, 6, 6, NULL);
  int *sr3 = searchRange(n3, 0, 0, NULL);
  for (int i = 0; i < 2; i++)
    printf("%d ", sr1[i]); // expect: 3 4
  printf("\n");
  for (int i = 0; i < 2; i++)
    printf("%d ", sr2[i]); // expect: -1 -1
  printf("\n");
  for (int i = 0; i < 2; i++)
    printf("%d ", sr3[i]); // expect: -1 -1
  printf("\n");
}