Consequently, in your binary search you are paying a large cost with all those recursive calls. Remember each call requires setting up a stack frame, copying all the parameters and initializing all the variables, plus for large arrays you could potentially use a lot of stack memory. (Not likely to be a problem on regular computers, but definitely in memory limited situations.)
function binary_search(A, n, T) is
L := 0
R := n − 1
while L ≤ R do
m := floor((L + R) / 2)
if A[m] < T then
L := m + 1
else if A[m] > T then
R := m − 1
else:
return m
return unsuccessfulYou might consider a simple example as to why recursion is the wrong approach here. Consider another potentially recursive problem -- calculating factorial. Factorial(n) is defined as all the integers between 1..n multiplied together. (So obviously it only works for integers and only works for numbers >=1.) You can define factorial like this:
function factorial(n) is
if n == 1 return 1;
else return n * factorial(n-1);
Is this correct? Yes, for sure but it is a terrible solution. All those extra function calls make it very expensive. You can instead simply define it as:
function factorial(n) is
int total = 1;
for(int i=2; i<=n; i++) total *= i;
return total;
Now in a for loop you don't have the huge cost of n function calls. This is because the function call's purpose is to store the intermediate state, and it isn't necessary. You can store it all in one variable.
FWIW, both the recursive factorial and your algorithm isbinary search algorithms are tail recursive, so I suppose some really aggressive optimizer might make the conversion automatically for you. But I doubt a C++ compiler could ever be that aggressive since it requires a lot of deep information about function side effects that is pretty hard to gather, and risky to assume. (If you were using a pure functional language, for example, you would give it as you have written, and the tail recursion would generally be optimized away.)
Consequently, you are paying a large cost with all those recursive calls. Remember each call requires setting up a stack frame, copying all the parameters and initializing all the variables, plus for large arrays you could potentially use a lot of stack memory. (Not likely to be a problem on regular computers, but definitely in memory limited situations.)
function binary_search(A, n, T) is
L := 0
R := n − 1
while L ≤ R do
m := floor((L + R) / 2)
if A[m] < T then
L := m + 1
else if A[m] > T then
R := m − 1
else:
return m
return unsuccessful
FWIW, your algorithm is tail recursive, so I suppose some really aggressive optimizer might make the conversion automatically for you. But I doubt a C++ compiler could ever be that aggressive since it requires a lot of deep information about function side effects that is pretty hard to gather, and risky to assume. (If you were using a pure functional language, for example, you would give it as you have written, and the tail recursion would generally be optimized away.)
Consequently, in your binary search you are paying a large cost with all those recursive calls. Remember each call requires setting up a stack frame, copying all the parameters and initializing all the variables, plus for large arrays you could potentially use a lot of stack memory. (Not likely to be a problem on regular computers, but definitely in memory limited situations.)
function binary_search(A, n, T) is
L := 0
R := n − 1
while L ≤ R do
m := floor((L + R) / 2)
if A[m] < T then
L := m + 1
else if A[m] > T then
R := m − 1
else:
return m
return unsuccessfulYou might consider a simple example as to why recursion is the wrong approach here. Consider another potentially recursive problem -- calculating factorial. Factorial(n) is defined as all the integers between 1..n multiplied together. (So obviously it only works for integers and only works for numbers >=1.) You can define factorial like this:
function factorial(n) is
if n == 1 return 1;
else return n * factorial(n-1);
Is this correct? Yes, for sure but it is a terrible solution. All those extra function calls make it very expensive. You can instead simply define it as:
function factorial(n) is
int total = 1;
for(int i=2; i<=n; i++) total *= i;
return total;
Now in a for loop you don't have the huge cost of n function calls. This is because the function call's purpose is to store the intermediate state, and it isn't necessary. You can store it all in one variable.
FWIW, both the recursive factorial and your binary search algorithms are tail recursive, so I suppose some really aggressive optimizer might make the conversion automatically for you. But I doubt a C++ compiler could ever be that aggressive since it requires a lot of deep information about function side effects that is pretty hard to gather, and risky to assume. (If you were using a pure functional language, for example, you would give it as you have written, and the tail recursion would generally be optimized away.)
My immediate reaction on reading this is "why is it recursive"? It has a bit of a feel for a recursive algorithm because it is divide and conquer, but there is really no need to do so here. What recursion provides is an easy way to manage the context of the intermediate parts. (For example, when sorting the array a recursive solution is good because you can solve the sub parts and then combine them, and the sub parts have distinct data that has to be managed.) But the data to be managed in binary search is trivial -- namely the lowest index of the part still being searched and the upper index of the part still being searched.
Consequently, you are paying a large cost with all those recursive calls. Remember each call requires setting up a stack frame, copying all the parameters and initializing all the variables, plus for large arrays you could potentially use a lot of stack memory. (Not likely to be a problem on regular computers, but definitely in memory limited situations.)
Here is the solution given in wikipedia. It is, you will see, pretty straightforward. The state is managed on only two variables - L and R, the leftmost and rightmost indexes of the space still being searched. Obviously you'd have to translate it into C++, but the translation is pretty straightforward.
function binary_search(A, n, T) is
L := 0
R := n − 1
while L ≤ R do
m := floor((L + R) / 2)
if A[m] < T then
L := m + 1
else if A[m] > T then
R := m − 1
else:
return m
return unsuccessful
FWIW, your algorithm is tail recursive, so I suppose some really aggressive optimizer might make the conversion automatically for you. But I doubt a C++ compiler could ever be that aggressive since it requires a lot of deep information about function side effects that is pretty hard to gather, and risky to assume. (If you were using a pure functional language, for example, you would give it as you have written, and the tail recursion would generally be optimized away.)
My immediate reaction on reading this is "why is it recursive"? It has a bit of a feel for a recursive algorithm because it is divide and conquer, but there is really no need to do so here. What recursion provides is an easy way to manage the context of the intermediate parts. (For example, when sorting the array a recursive solution is good because you can solve the sub parts and then combine them, and the sub parts have distinct data that has to be managed.) But the data to be managed in binary search is trivial -- namely the lowest index of the part still being searched and the upper index of the part still being searched.
Consequently, you are paying a large cost with all those recursive calls. Remember each call requires setting up a stack frame, copying all the parameters and initializing all the variables, plus for large arrays you could potentially use a lot of stack memory. (Not likely to be a problem on regular computers, but definitely in memory limited situations.)
Here is the solution given in wikipedia. It is, you will see, pretty straightforward. Obviously you'd have to translate it into C++, but the translation is pretty straightforward.
function binary_search(A, n, T) is
L := 0
R := n − 1
while L ≤ R do
m := floor((L + R) / 2)
if A[m] < T then
L := m + 1
else if A[m] > T then
R := m − 1
else:
return m
return unsuccessful
FWIW, your algorithm is tail recursive, so I suppose some really aggressive optimizer might make the conversion automatically for you. But I doubt a C++ compiler could ever be that aggressive since it requires a lot of deep information about function side effects that is pretty hard to gather, and risky to assume. (If you were using a pure functional language, for example, you would give it as you have written, and the tail recursion would generally be optimized away.)
My immediate reaction on reading this is "why is it recursive"? It has a bit of a feel for a recursive algorithm because it is divide and conquer, but there is really no need to do so here. What recursion provides is an easy way to manage the context of the intermediate parts. (For example, when sorting the array a recursive solution is good because you can solve the sub parts and then combine them, and the sub parts have distinct data that has to be managed.) But the data to be managed in binary search is trivial -- namely the lowest index of the part still being searched and the upper index of the part still being searched.
Consequently, you are paying a large cost with all those recursive calls. Remember each call requires setting up a stack frame, copying all the parameters and initializing all the variables, plus for large arrays you could potentially use a lot of stack memory. (Not likely to be a problem on regular computers, but definitely in memory limited situations.)
Here is the solution given in wikipedia. It is, you will see, pretty straightforward. The state is managed on only two variables - L and R, the leftmost and rightmost indexes of the space still being searched. Obviously you'd have to translate it into C++, but the translation is pretty straightforward.
function binary_search(A, n, T) is
L := 0
R := n − 1
while L ≤ R do
m := floor((L + R) / 2)
if A[m] < T then
L := m + 1
else if A[m] > T then
R := m − 1
else:
return m
return unsuccessful
FWIW, your algorithm is tail recursive, so I suppose some really aggressive optimizer might make the conversion automatically for you. But I doubt a C++ compiler could ever be that aggressive since it requires a lot of deep information about function side effects that is pretty hard to gather, and risky to assume. (If you were using a pure functional language, for example, you would give it as you have written, and the tail recursion would generally be optimized away.)
My immediate reaction on reading this is "why is it recursive"? It has a bit of a feel for a recursive algorithm because it is divide and conquer, but there is really no need to do so here. What recursion provides is an easy way to manage the context of the intermediate parts. (For example, when sorting the array a recursive solution is good because you can solve the sub parts and then combine them, and the sub parts have distinct data that has to be managed.) But the data to be managed in binary search is trivial -- namely the lowest index of the part still being searched and the upper index of the part still being searched.
Consequently, you are paying a large cost with all those recursive calls. Remember each call requires setting up a stack frame, copying all the parameters and initializing all the variables, plus for large arrays you could potentially use a lot of stack memory. (Not likely to be a problem on regular computers, but definitely in memory limited situations.)
Here is the solution given in wikipedia. It is, you will see, pretty straightforward. Obviously you'd have to translate it into C++, but the translation is pretty straightforward.
function binary_search(A, n, T) is
L := 0
R := n − 1
while L ≤ R do
m := floor((L + R) / 2)
if A[m] < T then
L := m + 1
else if A[m] > T then
R := m − 1
else:
return m
return unsuccessful
FWIW, your algorithm is tail recursive, so I suppose some really aggressive optimizer might make the conversion automatically for you. But I doubt a C++ compiler could ever be that aggressive since it requires a lot of deep information about function side effects that is pretty hard to gather, and risky to assume. (If you were using a pure functional language, for example, you would give it as you have written, and the tail recursion would generally be optimized away.)