algorithm - Search in ordered list -


assume have list 0, 10, 30, 45, 60, 70 sorted in ascending order. given number x how find number in list below it?

i looking efficient (faster) algorithm this, without of course having iterate through whole list.

ex: [0, 10, 30, 45, 60, 70]  given number 34, want return 30. given number 30, want return 30. given number 29, want return 10.

and forth.

  • if list indeed small, efficient way create array of size 71, initialize once arr[i] = answer, , in constant query time - answer. idea since possible set of queries limited, there no reason not pre-calculate , result pre-calculated data.

  • if cannot pre-process, , array small - linear scan efficient such small array, overhead of using complex algorithm not worth such small arrays. overhead more complex algorithms (like binary search) add lot of instructions per iteration, nullified small arrays. note log_2(6) < 3, , expected time (assuming uniform distribution) result in linear search, linear search simpler, each iteration faster in binary search.

pseudo code:

prev = -infinity (x in arr):    if x>arr:         return prev    prev = x
  • if array getting larger, use binary search. algorithm designed find value (or first value closest it) in sorted array, , runs in o(logn) time, needing traverse fewer elements entire list.
    it achieve better results (in terms of time performance) compared naive linear scan, assuming uniform distribution of queries.

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