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

×

# asking for logic of fake binary search problem

 0 can you please share your logic to solve fake binary search? link of problem asked 15 May, 22:35 96●1●6 accept rate: 33%

 1 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
 0 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. answered 16 May, 03:07 4★sorb1997 150●8 accept rate: 10%
 0 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
 toggle preview community wiki:
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