I hope I am not answering your homework, as it has been over a year since this question was asked. Here is a tail recursive solution that will take log(len(a)+len(b)) time. Assumption: The inputs are correct, i.e., k is in the range [0, len(a)+len(b)]. Base cases: If length of one of the arrays is 0, the answer … Read more
Here’s just an outline of the idea: In a BST, the left subtree of node T contains only elements smaller than the value stored in T. If k is smaller than the number of elements in the left subtree, the kth smallest element must belong to the left subtree. Otherwise, if k is larger, then … Read more
There is no such functions, but you can write a simple one using std::lower_bound, std::upper_bound or std::equal_range. A simple implementation could be template<class Iter, class T> Iter binary_find(Iter begin, Iter end, T val) { // Finds the lower bound in at most log(last – first) + 1 comparisons Iter i = std::lower_bound(begin, end, val); if … Read more
Here a more mathematical way of seeing it, though not really complicated. IMO much clearer as informal ones: The question is, how many times can you divide N by 2 until you have 1? This is essentially saying, do a binary search (half the elements) until you found it. In a formula this would be … Read more
bisect_left finds the first position p at which an element could be inserted in a given sorted range while maintaining the sorted order. That will be the position of x if x exists in the range. If p is the past-the-end position, x wasn’t found. Otherwise, we can test to see if x is there … Read more
You can use the localeCompare() method. string_a.localeCompare(string_b); /* Expected Returns: 0: exact match -1: string_a < string_b 1: string_a > string_b */ Further Reading: MDN: String.prototype.localeCompare Stack Overflow – Is there a JavaScript strcmp()? Tutorials Point: JavaScript String – localeCompare() Method