0

I'm having a ton of difficulty implementing a binary search. I know killed by server has to do something with the while loop, I just cant seem to pinpoint it. Also, I'm not sure why it is not finding the value in some circumstances. Any explanation regarding these issues would be much appreciated.

and yes, I have used searching, but I can't seem to find a solution and really would like understand why this is giving me output.

Thank you.

bool search(int value, int values[], int n) {

int left = -1;
int mid = left + (n - left) / 2; 

while(n - 1 >= left) {

    if(values[mid] < value) { 
           left = mid + 1; 
    } 
    else if(values[mid] > value) {
            mid =  n - 1; 

    } 
    else {
         return true; 
    }
} 
return false; 
}   






 void sort(int values[], int n)  {

  int swap; 
 //Outer loop iterates over the values[](starts at index 0)
 for(int i = 0; i <= n - 1; i++)  
{

   //inner loop iterates over array starting at index 1. 
    for(int j = 1; j <= n; j++) 
    {

        //checks if outer value is greater than inner value.
        if(values[i] > values[j]) 
        {

            //swap now holds the i'th char(outer) in the values array.
            swap = values[i];

            //now we can overide the i'th char(outer) with j'th char(inner).
            values[i] = values[j];

            //now we add the value in swap to j'th char(inner)
            values[j] = swap; 
        }
    }
}
}


Output:
  :) helpers.c compiles
  :( finds 42 in {42,43,44}
  \ killed by server
  :( finds 42 in {41,42,43}
  \ killed by server
  :) finds 42 in {40,41,42}
  :( finds 42 in {41,42,43,44}
  \ killed by server
  :) finds 42 in {40,41,42,43}
  :( finds 42 in {39,40,41,42}
  \ killed by server
  :( doesn't find 42 in {39,40,41}
  \ killed by server
  :( doesn't find 42 in {39,40,41,43}
  \ killed by server
  :( finds 42 in {42,40,39,41}
  \ killed by server 
1

Binary search means:

  1. You have a search interval, with left and right boundary.
  2. Is the interval empty?
    1. Yes => :( Value not found
    2. No => keep doing
  3. Calculate the middle index of the interval
  4. You evaluate the element at the middle index
    1. it's the value => Heureka!
    2. it's lower => place left boundary just right of the middle index
    3. it's higher => place right boundary just left of the middle index
  5. back to 2.

That's GOTO style, you'd use a while loop, like "while interval not empty", for steps 2 to 5.

And array elements are numbered from 0 to length-1, so make sure the array index never reaches the length, in sort your j might.

2
  • I think I understand - is the while loop I need to fix or is there more? And is my sort correct? I tried testing in just a bit confused with this.
    – ncubed
    Feb 23 '17 at 18:18
  • The while loop needs fixing, but you currently don't seem to have variables set up for the search interval boundaries. For sort, see last sentence of my answer, basically, use < instead of <=, otherwise you might access elements outside of the array.
    – Blauelf
    Feb 23 '17 at 18:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .