asking for logic of fake binary search problem

general
1

can you please share your logic to solve fake binary search?
link of problem

2

Here first find the index of element X in array.
Let A[]={1,4,2,5,9,8,3} and we have X=9. So it’s index is 5.
Now just trace the set of indices that binary search would have followed to reach index 5 in case array was sorted.
So indices traced would be like indices[]={4,6,5} . Here indices[] represent the indexes which would be visited by binary search. Now in above indices[] array first move is 4->6. This means that to return correct result element at a[4] should be less than X=9. Here a[4]=5 so this condition holds and no swap is required.

Now come to the move 6->5. This means that if we have to go from index 6 to 5 , then a[6]>X. Buthere a[6]=8<X. So one swap is required with some element greater than X. This is the logic.

Now for minimizing swaps , you can see that 8 in above e.g. needs to be swapped with some no greater than X. Also consider some testcase where a no larger than X has to be replaced by a number smaller than X. Then what we can do is to swap 8 with that number as the swap will fulfill the requirements of both the indices. This way you can minimize the no. of swaps

1 Like
3

I will just give you a hint because I believe with some intuition anyone can crack down the problem(If I did, you too can :)). Focus on one of the line of the question “You can not change the position of x”. What does this mean? That you have to somehow make the algorithm converge at the position of x(go to x, if you can not make it come to you :D). The algorithm that is applied in question is Binary Search which makes it’s decision of movement based on the value of the middle element(to be precise based on the comparison between the value at the middle position and the value to search). So keep track of of whether x lies to the left or right of the current middle and swap at the middle a correct value(greater or smaller so that the algorithms moves in the direction of x). There are some additional checks and bounds but I hope you are good to go with this much info.

4

Suppose the index of the element with value x is i, ar denotes the array and total of n elements. As the element x cannot be moved, the only option left is to manipulate values at all the intermediate indexes j, if necessary, where comparisons are made during binary search such that ar[j] < x if 0<= j < i and ar[j] > x, if i<j<=n-1, if possible.