recursion - Design of an algorithm problems of Clog n[C++ code] -


two sorted arrays of integers a[1..n] , b[1..n] provided in ascending order.

q:design o(log n)-time algorithm finding out median of 2n integers. n may not power of 2.

to make thing easy, can assume o(1) algorithm return m such that:

2^m < n <  2^m+1

my problems:

  1. n may not power of 2, mean? (understood)
  2. i don't know how change input , make length power of 2 after found min , max elements both array a , b.

you can solve in o(logn) time using binary search style approach. consider following 2 arrays:

1 1 2 2 3 1 2 3 4 5

now combined median is:

1 1 1 2 2 2 3 3 4 5 => 2

let's see how can find it. start guessing median center of each array:

1 1 2 2 3 => 2 1 2 3 4 5 => 3

logically, know combined median can't possibly less 2 or greater 3. rather, must somewhere in between these 2 values. can discard in first array smaller 2 , in second array larger 3. won't affect position of median because discarding equal number of elements on both sides of combined median is. conceptually, leaves with:

2 2 3 => 2 1 2 3 => 2

now have agreeing median, basic idea keep discarding half of entries in each of 2 arrays until have single median value.

this algorithm perform binary search, o(logn).


Comments

Post a Comment

Popular posts from this blog

PHP and MySQL WP -

i trying accomplish 2 things here code. writing php directly wp page using insert php plugin. 1) query mysql database , return results 1 column 4 columns. 2) make each result own hyperlink directs user new wp page runs new query on page. i able query show results , turn results dynamic hyperlink, cannot formatting down. right returns result 1 column. here have: [insert_php] $servername = "localhost"; $username = "login"; //edited privacy $password = "password"; //edited privacy $database = "database"; //edited privacy // create connection $conn = new mysqli($servername, $username, $password, $database); // check connection if ($conn->connect_error) { die("connection failed: " . $conn->connect_error); } echo "connected successfully"; //get results database $result = mysqli_query($conn,"select mine mines order mine"); $all_property = array(); //declare array saving property //showing proper...
Read more

android - InAppBilling registering BroadcastReceiver in AndroidManifest -

i'm implementing inapp billing in android app. works well, however, i'm trying decouple broadcast receiver activity manifest. suggestion in android's trivialdrive sample: // important: dynamically register broadcast messages updated purchases. // register receiver here instead of <receiver> in manifest // because call getpurchases() @ startup, therefore can ignore // broadcasts sent while app isn't running. // note: registering listener in activity bad idea, done here // because sample. regardless, receiver must registered after // iabhelper setup, before first call getpurchases(). currently there's class extends broadcastreceiver : public class iabbroadcastreceiver extends broadcastreceiver { /** * intent action receiver should filter for. */ public static final string action = "com.android.vending.billing.purchases_updated"; private final iabbroadcastlistener mlistener; public iabbroadcastreceiver(iabbroadcastlistener listener) { m...
Read more

go - golang pprof for c library code -

i have been trying profile golang application pprof, seems details of c code(linked static library) missed in output result. flame graph from frame graph can see c code time consuming reported within "runtime._externalcode", no details @ all. , sure static library compiled debug enable. so there way make pprof details(like stack trace) of 3rd party c code? or there other golang profiling tool this?
Read more