aboutsummaryrefslogtreecommitdiff
path: root/search_insert_pos.c
blob: cbbdcd96a88d08495978d5858132bc15a3253729 (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
// 35. Search Insert Position
#include <stdio.h>
#include <stdlib.h>

/*
 * given a sorted array of distinct intergers and a target value, return the
 * index if the target is found. if not, return the index where it would be if
 * it were inserted in order. must be o(ln) compexity
 */

int searchInsert(int *nums, int numsSize, int target) {
  int left = 0, right = numsSize, mid;
  while (left < right) {
    mid = left + (right - left) / 2;
    if (nums[mid] >= target)
      right = mid;
    else
      left = mid + 1;
  }
  return left;
}

int main() {
  int nums[] = {1, 3, 5, 6}, ns = 4;
  printf("%d\n", searchInsert(nums, ns, 5)); // expect: 2
  printf("%d\n", searchInsert(nums, ns, 2)); // expect: 1
  printf("%d\n", searchInsert(nums, ns, 7)); // expect: 4
}