# Accepted C solution with binary search in 4ms

• ``````typedef struct Node {
int value;
int pos;
} Node;

int cmp(const void* a, const void* b) {
return ((Node*)a)->value - ((Node*) b)->value;
}

// recusively binary search for a node which + baseNode = target
int* twoSumHelper(Node* nodeArr, int start_pos, int end_pos, Node* baseNode, int target) {
int pos = (start_pos + end_pos) / 2;
int sum = nodeArr[pos].value + baseNode->value;
if (sum == target) {
int* result = malloc(sizeof(int) * 2);
result[0] = baseNode->pos;
result[1] = nodeArr[pos].pos;
return result;
} else {
if (start_pos == end_pos) {
return NULL;
}

if (sum > target){
return twoSumHelper(nodeArr, start_pos, pos, baseNode, target);
} else {
return twoSumHelper(nodeArr, pos + 1, end_pos, baseNode, target);
}
}
}

int* twoSum(int* nums, int numsSize, int target) {
Node* nodeArr = malloc(sizeof(Node) * numsSize);
int i;
for (i = 0; i < numsSize; i++) {
nodeArr[i] = (Node){
.value = nums[i],
.pos = i + 1,
};
}
qsort(nodeArr, numsSize, sizeof(Node), cmp);
int* result;
for (i = 0; i < numsSize; i++) {
result = twoSumHelper(nodeArr, i+1, numsSize - 1, &nodeArr[i], target);
if (result) {
free(nodeArr);

// sort result
if (result[0] > result[1]) {
result[0] = result[0] + result[1];
result[1] = result[0] - result[1];
result[0] = result[0] - result[1];
}
return result;
}
}
}``````

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