Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Find time complexity of binary search.
int binary_search(vector<int> a, int low, int high, int key) { // T(n)
if (low > high) { // 1
return -1; // 1
}
int mid = (low+high)/2; // 1
if (a[mid] == key) { // 1
return mid; // 1
}
if (a[mid] < key) { // 1
return binary_search(a, mid+1, high, key); // T(n/2)
} else { // 1
return binary_search(a, low, mid-1, key); // T(n/2)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment