Bsrgvty

Is it appropriate to send out a manuscript under review to a professor?

Meaning/translation of title "The Light Fantastic" By Terry Pratchett

How come the Russian cognate for the Czech word "čerstvý" (fresh) means entirely the opposite thing (stale)?

Would it be easier to colonise a living world or a dead world?

D&D Monsters and Copyright

Landing Hero: Product snippets VS illustrations

Should I withdraw my paper because the Editor is behaving so badly with me?

How do lasers measure short distances (<1cm) when electronics are too slow for time-of-flight to work?

Why didn't he give Sam the antidote?

Does UPDATE without WHERE clause lock a table in PostgreSQL?

Why has Donald Trump's popularity remained so stable over a rather long period of time?

Why didn't Trudy wear a breathing mask in Avatar?

What if a quote contains an error

Coffee Grounds and Gritty Butter Cream Icing

How acceptable is an ellipsis "..." in formal mathematics?

Why would they pick a gamma distribution here?

How create a general legend which always remain on top of the plot

Generalized Assignment Problem as the sub-problem

How long could a human survive completely without the immune system?

Translation Golf XLVIII — We're sorry to see you go

Should I reveal productivity tricks to peers, or keep them to myself in order to be more productive than the others?

Had there been instances of national states banning harmful imports before the mid-19th C Opium Wars?

Ways to bypass spell resistance in 5e?

Self-learning Calculus. Where does Lang's First Course in Calculus stay when compared to Apostol/Spivak/Courant

Finding the upper and lower bound using binary search

Converting string elements of an array to upper and lower case, maintaining names of keysFinding the shortest excerpt that contains all search termsFinding the maximum distance from the starting nodeHackerrank Lower Bound-STLBinary search for IOI problem: CaveInefficient binary search? Hackerrank - Climbing the LeaderboardMatrix class with space-optimized triangular (lower and upper) variants

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty
margin-bottom:0;

5

$begingroup$

I am trying to solve this InterviewBit question
https://www.interviewbit.com/problems/search-for-a-range/.

My code for this seems to be working properly and it does give me the correct answers on my IDE and on all the sample test cases online but it gives me a TLE on the online judge. It runs in O(log n) time, just a variation of simple binary search.

I am trying to understand what aspect of my code could be made more efficient and faster.

Here's my code:

int findBound(vector<int> a, int b, bool lower)
int low=0, high=a.size()-1, mid;
while(low<=high)
 mid=low+(high-low)/2;
 if(a[mid]==b)
 if(lower)
 if((mid != (a.size()-1)) && a[mid+1]==b)
 low=mid+1;
 else
 return mid;
 
 else
 if(mid != 0 && a[mid-1]==b)
 high=mid-1;
 else
 return mid;
 
 
 else if(a[mid]>b)
 high=mid-1;
 else if(a[mid]<b)
 low=mid+1;

return -1;


vector<int> Solution::searchRange(const vector<int> &A, int B) 
 vector<int> ans(2);
 ans[0]=findBound(A, B, true);
 ans[1]=findBound(A, B, false);
 return ans;

c++ programming-challenge time-limit-exceeded complexity

share|improve this question

edited Apr 17 at 12:00

Graipher

30.7k66 gold badges4848 silver badges106106 bronze badges

asked Apr 17 at 8:14

Karan SinghKaran Singh

14133 bronze badges

$endgroup$

add a comment
 | 

5

$begingroup$

I am trying to solve this InterviewBit question
https://www.interviewbit.com/problems/search-for-a-range/.

My code for this seems to be working properly and it does give me the correct answers on my IDE and on all the sample test cases online but it gives me a TLE on the online judge. It runs in O(log n) time, just a variation of simple binary search.

I am trying to understand what aspect of my code could be made more efficient and faster.

Here's my code:

int findBound(vector<int> a, int b, bool lower)
int low=0, high=a.size()-1, mid;
while(low<=high)
 mid=low+(high-low)/2;
 if(a[mid]==b)
 if(lower)
 if((mid != (a.size()-1)) && a[mid+1]==b)
 low=mid+1;
 else
 return mid;
 
 else
 if(mid != 0 && a[mid-1]==b)
 high=mid-1;
 else
 return mid;
 
 
 else if(a[mid]>b)
 high=mid-1;
 else if(a[mid]<b)
 low=mid+1;

return -1;


vector<int> Solution::searchRange(const vector<int> &A, int B) 
 vector<int> ans(2);
 ans[0]=findBound(A, B, true);
 ans[1]=findBound(A, B, false);
 return ans;

c++ programming-challenge time-limit-exceeded complexity

share|improve this question

edited Apr 17 at 12:00

Graipher

30.7k66 gold badges4848 silver badges106106 bronze badges

asked Apr 17 at 8:14

Karan SinghKaran Singh

14133 bronze badges

$endgroup$

add a comment
 | 

$begingroup$

I am trying to solve this InterviewBit question
https://www.interviewbit.com/problems/search-for-a-range/.

My code for this seems to be working properly and it does give me the correct answers on my IDE and on all the sample test cases online but it gives me a TLE on the online judge. It runs in O(log n) time, just a variation of simple binary search.

I am trying to understand what aspect of my code could be made more efficient and faster.

Here's my code:

int findBound(vector<int> a, int b, bool lower)
int low=0, high=a.size()-1, mid;
while(low<=high)
 mid=low+(high-low)/2;
 if(a[mid]==b)
 if(lower)
 if((mid != (a.size()-1)) && a[mid+1]==b)
 low=mid+1;
 else
 return mid;
 
 else
 if(mid != 0 && a[mid-1]==b)
 high=mid-1;
 else
 return mid;
 
 
 else if(a[mid]>b)
 high=mid-1;
 else if(a[mid]<b)
 low=mid+1;

return -1;


vector<int> Solution::searchRange(const vector<int> &A, int B) 
 vector<int> ans(2);
 ans[0]=findBound(A, B, true);
 ans[1]=findBound(A, B, false);
 return ans;

c++ programming-challenge time-limit-exceeded complexity

share|improve this question

edited Apr 17 at 12:00

Graipher

30.7k66 gold badges4848 silver badges106106 bronze badges

asked Apr 17 at 8:14

Karan SinghKaran Singh

14133 bronze badges

$endgroup$

int findBound(vector<int> a, int b, bool lower)
int low=0, high=a.size()-1, mid;
while(low<=high)
 mid=low+(high-low)/2;
 if(a[mid]==b)
 if(lower)
 if((mid != (a.size()-1)) && a[mid+1]==b)
 low=mid+1;
 else
 return mid;
 
 else
 if(mid != 0 && a[mid-1]==b)
 high=mid-1;
 else
 return mid;
 
 
 else if(a[mid]>b)
 high=mid-1;
 else if(a[mid]<b)
 low=mid+1;

return -1;


vector<int> Solution::searchRange(const vector<int> &A, int B) 
 vector<int> ans(2);
 ans[0]=findBound(A, B, true);
 ans[1]=findBound(A, B, false);
 return ans;

share|improve this question

edited Apr 17 at 12:00

Graipher

30.7k66 gold badges4848 silver badges106106 bronze badges

asked Apr 17 at 8:14

Karan SinghKaran Singh

14133 bronze badges

share|improve this question

edited Apr 17 at 12:00

Graipher

30.7k66 gold badges4848 silver badges106106 bronze badges

asked Apr 17 at 8:14

Karan SinghKaran Singh

14133 bronze badges

edited Apr 17 at 12:00

Graipher

30.7k66 gold badges4848 silver badges106106 bronze badges

edited Apr 17 at 12:00

Graipher

30.7k66 gold badges4848 silver badges106106 bronze badges

asked Apr 17 at 8:14

Karan SinghKaran Singh

14133 bronze badges

asked Apr 17 at 8:14

Karan SinghKaran Singh

14133 bronze badges

1 Answer
1

active

oldest

votes

8

$begingroup$

I am trying to understand what aspect of my code could be made more efficient and faster.

First, the low hanging fruits...

• 
  

  You unnecessarily copy the sequence of integers when passing it to findBound:

  
  
  

  int findBound(vector<int> a, int b, bool lower)
  

  
  
  

  should be

  
  
  

  int findBound(const vector<int>& a, int b, bool lower)
  

  
  


• 
  

  You dispatch on the bool lower flag in every iteration of the main while-loop:

  
  
  

  if(lower) 
   /* ... */
   else 
   /* ... */
  
  

  
  
  

  Consider implementing two separate functions for the starting and one for the end index of the range.

  
  



• In one of the if-conditions in the middle of the main loop, you compute a.size() - 1. This could be done once at the top of the function and bound to a const-qualified variable. No need to evaluate this in every iteration.

Now, the crucial step...

• 
  

  You are doing unnecessary work when comparing values. The very first if-condition,

  
  
  

  if(a[mid]==b) { // ...
  

  
  
  

  tests for the branch with the least likelihood. Instead, check for a[mid] < b and nothing more. If you're wondering how this can be sufficient, check out this part of Sean Parent's Pacific C++ talk from 2018.

  
  

share|improve this answer

answered Apr 17 at 9:19

lubgrlubgr

93899 bronze badges

$endgroup$

add a comment
 | 

Your Answer

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "196"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/4.0/"u003ecc by-sa 4.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f217610%2ffinding-the-upper-and-lower-bound-using-binary-search%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

8

$begingroup$

I am trying to understand what aspect of my code could be made more efficient and faster.

First, the low hanging fruits...

• 
  

  You unnecessarily copy the sequence of integers when passing it to findBound:

  
  
  

  int findBound(vector<int> a, int b, bool lower)
  

  
  
  

  should be

  
  
  

  int findBound(const vector<int>& a, int b, bool lower)
  

  
  


• 
  

  You dispatch on the bool lower flag in every iteration of the main while-loop:

  
  
  

  if(lower) 
   /* ... */
   else 
   /* ... */
  
  

  
  
  

  Consider implementing two separate functions for the starting and one for the end index of the range.

  
  



• In one of the if-conditions in the middle of the main loop, you compute a.size() - 1. This could be done once at the top of the function and bound to a const-qualified variable. No need to evaluate this in every iteration.

Now, the crucial step...

• 
  

  You are doing unnecessary work when comparing values. The very first if-condition,

  
  
  

  if(a[mid]==b) { // ...
  

  
  
  

  tests for the branch with the least likelihood. Instead, check for a[mid] < b and nothing more. If you're wondering how this can be sufficient, check out this part of Sean Parent's Pacific C++ talk from 2018.

  
  

share|improve this answer

answered Apr 17 at 9:19

lubgrlubgr

93899 bronze badges

$endgroup$

add a comment
 | 

8

$begingroup$

I am trying to understand what aspect of my code could be made more efficient and faster.

First, the low hanging fruits...

• 
  

  You unnecessarily copy the sequence of integers when passing it to findBound:

  
  
  

  int findBound(vector<int> a, int b, bool lower)
  

  
  
  

  should be

  
  
  

  int findBound(const vector<int>& a, int b, bool lower)
  

  
  


• 
  

  You dispatch on the bool lower flag in every iteration of the main while-loop:

  
  
  

  if(lower) 
   /* ... */
   else 
   /* ... */
  
  

  
  
  

  Consider implementing two separate functions for the starting and one for the end index of the range.

  
  



• In one of the if-conditions in the middle of the main loop, you compute a.size() - 1. This could be done once at the top of the function and bound to a const-qualified variable. No need to evaluate this in every iteration.

Now, the crucial step...

• 
  

  You are doing unnecessary work when comparing values. The very first if-condition,

  
  
  

  if(a[mid]==b) { // ...
  

  
  
  

  tests for the branch with the least likelihood. Instead, check for a[mid] < b and nothing more. If you're wondering how this can be sufficient, check out this part of Sean Parent's Pacific C++ talk from 2018.

  
  

share|improve this answer

answered Apr 17 at 9:19

lubgrlubgr

93899 bronze badges

$endgroup$

add a comment
 | 

$begingroup$

I am trying to understand what aspect of my code could be made more efficient and faster.

First, the low hanging fruits...

• 
  

  You unnecessarily copy the sequence of integers when passing it to findBound:

  
  
  

  int findBound(vector<int> a, int b, bool lower)
  

  
  
  

  should be

  
  
  

  int findBound(const vector<int>& a, int b, bool lower)
  

  
  


• 
  

  You dispatch on the bool lower flag in every iteration of the main while-loop:

  
  
  

  if(lower) 
   /* ... */
   else 
   /* ... */
  
  

  
  
  

  Consider implementing two separate functions for the starting and one for the end index of the range.

  
  



• In one of the if-conditions in the middle of the main loop, you compute a.size() - 1. This could be done once at the top of the function and bound to a const-qualified variable. No need to evaluate this in every iteration.

Now, the crucial step...

• 
  

  You are doing unnecessary work when comparing values. The very first if-condition,

  
  
  

  if(a[mid]==b) { // ...
  

  
  
  

  tests for the branch with the least likelihood. Instead, check for a[mid] < b and nothing more. If you're wondering how this can be sufficient, check out this part of Sean Parent's Pacific C++ talk from 2018.

  
  

share|improve this answer

answered Apr 17 at 9:19

lubgrlubgr

93899 bronze badges

$endgroup$

share|improve this answer

answered Apr 17 at 9:19

lubgrlubgr

93899 bronze badges

answered Apr 17 at 9:19

lubgrlubgr

93899 bronze badges

answered Apr 17 at 9:19

lubgrlubgr

93899 bronze badges