Reversal algorithm

1

I know what is reversal algorithm and I know how it works. but I want to know why it works??
Can someone help me out??

2

I know what is Binary Search and I know how it works. But I want to know why it works??
Can you help me out??
If you can help me, I can help you.

3

binary search works because data is sorted and we are sure if the element to be searched is greater than a[mid] then ans will not be on the left side and vice versa.

If u don’t want to help, don’t help. I’m not here to listen to your lame answers.

1 Like
4

Okay, I would like to help you (seriously). Can you specify what exactly you mean by “Reversal Algorithm”.
String Reversal?
Array Reversal?
LinkedList Reversal?
Or what?
And look how your question sounds.

1 Like
5

Array reversal. (It can also be applied to strings)

And sorry if I was not clear with my question.
I’m talking about the following algorithm.

https://www.geeksforgeeks.org/program-for-array-rotation-continued-reversal-algorithm/

Basically I’m asking for proof.

6 
Let an array R be composed of two subarrays A and B i.e. R=A+B

Let our reverse function be rev().

Then, rev(R)=rev(A+B)=rev(B)+rev(A) ---(1)

E.g. R=1,2,3,4,5,6,7. Let A=1,2,3 and B=4,5,6,7
Then rev(R)=7,6,5,4,3,2,1 viz. rev(B) + rev(A)

Now as per the question, let R be rotated d times.
Let A=R[1..d] and B=[d+1..n]

We go by the reversal algorithm. After reversal of A and B, R=rev(A)+rev(B)
Thus, applying equation (1), rev(R)=rev(rev(A)+rev(B))=rev(rev(B))+rev(rev(A))=B+A

Hence our array R gets rotated by the algo.

Note that this + is not the arithmetic one, but is used here to signify array concatenation i.e. A+B != B+A
2 Likes