MHB Find First Free Position in Array in $O(\log n)$ Time Complexity

  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Position
Click For Summary
To find the first free position in an array efficiently, a binary search approach is suggested, with the function `FreePos` designed to operate in O(log n) time complexity. The function checks for the presence of `INT_MAX` to identify free positions, and modifications have been made to handle edge cases and avoid segmentation faults. Users discuss potential issues causing segmentation faults when calling `FreePos`, emphasizing the importance of ensuring that the input array is correctly defined and indexed. The conversation includes iterative improvements to the function and clarifications on handling specific conditions within the array. The final version of `FreePos` is confirmed to be effective for the intended merging of star systems.
  • #31
mathmari said:
Should I declare [m]starsystem[/m] outside the if?? (Wondering)

The would help yes.
The life time of an object ends when we get to the matching closing brace. (Nerd)
 
Technology news on Phys.org
  • #32
I like Serena said:
The life time of an object ends when we get to the matching closing brace. (Nerd)

What do you mean?? (Wondering)
 
  • #33
mathmari said:
What do you mean?? (Wondering)

When you have:
Code:
void function()
{
  int a = 2;
  {
    int a = 3;
    printf("%d\n", a);
  }
  printf("%d\n", a);
}
what do you think gets printed? (Wondering)
 
  • #34
I like Serena said:
When you have:
Code:
void function()
{
  int a = 2;
  {
    int a = 3;
    printf("%d\n", a);
  }
  printf("%d\n", a);
}
what do you think gets printed? (Wondering)

It will print:

3
2

right?? (Wondering)
 
  • #35
mathmari said:
It will print:

3
2

right?? (Wondering)

Yep. (Nod)

When "int a = 3" is declared, local stack memory is allocated for it.
Furthermore it "hides" the "a" that was declared earlier.
When the closing brace comes by, the local stack memory is automatically released.
Afterwards, the original "a" becomes visible again. (Nerd)
 
  • #36
I like Serena said:
Yep. (Nod)

When "int a = 3" is declared, local stack memory is allocated for it.
Furthermore it "hides" the "a" that was declared earlier.
When the closing brace comes by, the local stack memory is automatically released.
Afterwards, the original "a" becomes visible again. (Nerd)

Ahaa... Ok! (Muscle)I have also an other question...

When I declare 'starsystem', before the if statement, do I write it as followed??

[m] starsy_t *starsystem;[/m]

Or should I set it equal to [m]NULL[/m] ??

(Wondering)
 
  • #37
mathmari said:
Ahaa... Ok! (Muscle)I have also an other question...

When I declare 'starsystem', before the if statement, do I write it as followed??

[m] starsy_t *starsystem;[/m]

Or should I set it equal to [m]NULL[/m] ??

(Wondering)

It is good practice to always set a pointer to NULL if you're not setting it to any other specific value. (Smirk)
 

Similar threads

  • · Replies 12 ·
Replies
12
Views
2K
Replies
7
Views
2K
  • · Replies 4 ·
Replies
4
Views
2K
Replies
12
Views
2K
  • · Replies 98 ·
4
Replies
98
Views
14K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 20 ·
Replies
20
Views
4K
  • · Replies 20 ·
Replies
20
Views
5K
  • · Replies 1 ·
Replies
1
Views
2K