You are not logged in. Please login at www.codechef.com to post your questions!

×

asking for logic of fake binary search problem

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

asked 15 May, 22:35

nitish235's gravatar image

4★nitish235
9616
accept rate: 33%


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

link

answered 15 May, 23:27

lakh's gravatar image

4★lakh
1395
accept rate: 23%

edited 15 May, 23:30

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.

link

answered 16 May, 03:07

sorb1997's gravatar image

4★sorb1997
1508
accept rate: 10%

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.

link

answered 16 May, 14:34

dbot_5's gravatar image

4★dbot_5
11
accept rate: 0%

edited 16 May, 14:39

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×29

question asked: 15 May, 22:35

question was seen: 348 times

last updated: 16 May, 14:39