algorithm - Searching for an element in log(n) time -


i came across following question:

suppose modify given sorted list of 4n distinct numbers follows:

keep elements in positions (positions 2, 4, 6, ... 4n) are. form n disjoint pairs (i,j) on odd numbered positions = 2k+1 k = 0 n−1 , j = 2k+1 k = n 2n−1.

now swap elements in positions , j every such pair. (i.e. every element in odd numbered position in first half of array swapped element in odd numbered position in second half of array. no element involved in more 1 swap (i.e. swaps disjoint). don’t know these (i,j) pairs except element in odd numbered position in first half of array swapped element in odd numbered position in second half. given element x, explain how can determine whether or not x in (new reshuffled) array in o(logn) time.

honestly, not sure how approach one. given x, can search whether exists @ numbered position using binary search. numbers in odd positions no longer sorted.

any appreciated. thanks!

you can determine whether element x in new (shuffled) set doing 2 binary searches. key here odd elements act "keys" each other, since have been swapped in disjoint pairs.

  1. use standard binary search x, making sure choose even indices comparison. (using indices crucial, because elements still in order.)

  2. if x in array @ index, found. if not, find 2 elements m , n such m < x < n , index(n) - index(m) == 2. means if array still sorted, x have element between m , n (if in array).

  3. consider element @ index between m , n - call y. if element x in original array, must have been swapped y when creating shuffled array.

  4. perform second binary search y, again ensuring choose even indices comparison. step 2, find 2 elements m' , n' such m' < y < n' , index(n') - index(m') == 2. if array still sorted, element y element between m' , n'.

  5. the element between m' , n' must whichever element swapped y, , therefore whatever element between m , n. if value not x, x not exist in array.


Comments

Post a Comment

Popular posts from this blog

php - failed to open stream: HTTP request failed! HTTP/1.0 400 Bad Request -

this code i'm using find latitude , longitude of place: function coords($address){ echo $url="http://maps.googleapis.com/maps/api/geocode/json?address=".$address; $json = file_get_contents(urlencode($url)); $data = json_decode($json, true); print_r($data['results'][0]['geometry']['location']['lat']); print_r($data['results'][0]['geometry']['location']['lng']); } however returns warning: failed open stream: http request failed! http/1.0 400 bad request if use above code in simple procedure works fine not in function. note: have tried curl_init()... method produced same result? instead of encoding whole url encode address part. following code work fine $add='jamshoro phase 2'; $url="http://maps.googleapis.com/maps/api/geocode/json?address=".urlencode($add); $json = file_get_contents($url); $data = json_decode($json, true); print_r($data['r
Read more

java - How to filter a backspace keyboard input -

i have code gives message when key number pressed: txtvalueofclause.addeventfilter(keyevent.key_typed, new eventhandler<keyevent>() { @override public void handle(keyevent t) { char ar[] = t.getcharacter().tochararray(); char ch = ar[t.getcharacter().tochararray().length - 1]; if (!(ch >= '0' && ch <= '9')) { system.out.println("the char entered not number"); t.consume(); } } }); now if press on wrong button , press backspace remove it, error message. how can add backspace input if statement? i have found answer: txtvalueofclause.addeventfilter(keyevent.key_typed, new eventhandler<keyevent>() { @override public void handle(keyevent t) { char ar[] = t.getcharacter().tochararray(); char ch = ar[t.getcharacter().tochar
Read more

java - Show Soft Keyboard when EditText Appears -

i have code in android app, alert dialog , keyboard, , when dialog shown want keyboard appear. not , not sure why? here code: final alertdialog.builder alert = new alertdialog.builder(this); alert.settitle("title"); alert.setmessage("message"); final edittext input = new edittext(this); input.setinputtype(inputtype.type_class_number); alert.setview(input); input.setonfocuschangelistener(new view.onfocuschangelistener() { @override public void onfocuschange(view v, boolean hasfocus) { if (hasfocus) { log.i(tag, "in focus"); inputmethodmanager inputmethodmanager = (inputmethodmanager) getsystemservice(context.input_method_service); inputmethodmanager.showsoftinput(input, inputmethodmanager.show_implicit); } } }); but keyboard not appear though edit text in focus, , tell appear why, doesn't come up? thanks in advance.
Read more