# PSET3 find having trouble. Can someone help?

For some reason bubble sort is not working. Can someone help.

``````binary search bool search (int target, int array[],int length)
{
int end =  length-1; int start = 0;

while (array[start] <  array[end])
{
//   7           0          14
//  11           8          14
//  13          12      +   14
//  14          14          14
//
//   9           10      +    8    =
//               8       +   8
int middle  = (start + end)/2;
if (array[middle] ==  target)
{
return true;
}   //13.5         7
// 13.5           11
//13.5            13

if (  target > array[middle] )
{    // 8      7+1
// 12      11+1
// 14       13+1
start = middle+1;
//          8             13.5
//          12            13.5
if (array[start] ==  target)
{
return true;
}
}
else if(target < array[middle])
{

end = middle - 1;
if (array[end] ==  target)
{
return true;
}

}
}
return false;

}
``````

I realize bubble sort is really inefficient code. The code won't work . The parts I can identity is printf( "%d" , array[total]); and break; Will break work the way I set it up? Here is a few steps.

I just realized I don't even need this part. //reverses left and right back to correct order so right is not before left // 1 = 2 left = right; right = left + 1;

``````                                 r
l
// ex array[total] = {2,5,3,1,4}

l
r
// ex array[total] = {2,1,3,5,4}
``````

The next time I run the loop array[right] and array[left] will array[total] eventually change to {1 2 3 4 5}

//bubble sort

``````void sort (int array[], int  total ) { // ex array[total] = {2,5,3,1,4} int  end = total - 1; int left = 0; int min = 0; int right
=  left + 1;
while ((left <= total) || (min <= total))
{
if( array[left] > array[right] )
{//switches array[left] and array[right]
//5               3
array[left]  =  array[right];
//          5 -

array[right] = array[left]-1;
printf( "%d %d" ,array[left] ,array[right]);
//reverses left and right   back to correct order so right is not before left
// 1 =  2
left = right;
right = left + 1;

}
// maybe top block
if (right == end)
{
min++;
left = 0;
right = left +1;
}

if (min == end)// does total need to be end
{
printf( "%d" , array[total]);
break;
}
left++;
right = left + 1;

}

}
``````

Did I make any other mistakes in bubble sort?

``````:) helpers.c exists.
:) helpers.c compiles.
:( sorts {5,4,3,2,1}
expected "2", not "\n"
:( sorts {5,3,1,2,4,6}
expected "3", not "\n4\n6\n"
:( finds 28 in {28,29,30}
expected exit code 0, not 1
:( finds 28 in {27,28,29}
expected exit code 0, not 1
:( finds 28 in {26,27,28}
expected exit code 0, not 1
:( finds 28 in {27,28,29,30}
expected exit code 0, not 1
:( finds 28 in {26,27,28,29}
expected exit code 0, not 1
:( finds 28 in {25,26,27,28}
expected exit code 0, not 1
:) doesn't find 28 in {25,26,27}
:) doesn't find 28 in {25,26,27,29}
:) doesn't find 28 in {29,30,31,32}
:) doesn't find 28 in {29, 30, 31}
:( finds 28 in {30,27,28,26}
expected exit code 0, not 1
``````

The

``````array[start] <  array[end]
``````

is the wrong condition. You want to keep looping as long as the search interval has elements, so use

``````start <= end
``````

instead (`<=` as you chose both start and end to be included in the interval). Then you can remove those `if (array[start] == target)` and `if (array[end] == target)` which seem to compensate for leaving the loop early (and won't work if your array for example had only one element).

In `sort`,

``````        array[left]  =  array[right];
array[right] = array[left]-1;
``````

won't swap two elements. The usual way is using an extra variable, like

``````        int temp     = array[left];
array[left]  = array[right];
array[right] = temp;
``````

though there exist other schemes which don't need the extra variable but do some calculation instead (and are usually not as readable), for example

``````        array[left]  ^= array[right];
array[right] ^= array[left];
array[left]  ^= array[right];
``````

The

``````        left = right;
right = left + 1;
``````

should not be within the `if( array[left] > array[right] )` block, but below (otherwise you might skip a pair after swapping), and there should not be an extra copy of those two lines at the end of the loop. You'd have to use `if (left == end)` instead of `if (right == end)`. Instead of `if (left == end);` you could use `if (left == end - min)`.

You could use nested for loops instead of this complicated while loop. Those are meant to concentrate the loop control within one line, while the control of a while loop may be (and in your case is) spread over the whole body. So instead of

``````int end = total-1;
int left = 0;
int min = 0;
int right = 1;
while (true) // I don't think your condition will ever become false
{
if (array[left] > array[right])
{
// swap left and right element
}
left++;
right++;
if (left == end - min)
{
min++;
left = 0;
right = left + 1;
}
if (min == end)
{
break;
}
}
``````

you could have

``````for (int min = 0; min < total - 1; min++)
{
for (int left = 0, right = left + 1; right < total - min; left++, right++)
{
if (array[left] > array[right])
{
// swap left and right element
}
}
}
``````

(though I would substitute every use of `right` with `left+1`, as those always move together)

Oh, and I'm not sure, your `printf` might confuse `check50`, maybe you need to remove those before submission.

• For Search I don't really understand how you can get rid of the stuff you said. What happens start = 0 to end = 14 and target = 8. It will skip 8. Am I wrong? – user20243 Oct 7 '17 at 5:43
• can you help @Blauelf – user20243 Oct 7 '17 at 5:58
• You say initial search interval is (0, 14) and target is found at index 8, larger than `array[middle]`. So on next iteration you'd have (8, 14), then (8, 10), then (8, 8), at which point `middle` has reached 8. That case of an interval with one element is the reason why you need `<=` and not `<` in the while's condition. – Blauelf Oct 9 '17 at 8:29

@Blauelf

I accidentally lost the info for the previous account and how to recover it. So I typed in the code but am still getting errors I assume it is something I am doing wrong. Without the code below it works and compile. Can you help me find the error? I have tried help50 and get nothing.

``````clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm
/tmp/helpers-e977f1.o: In function `search':
/home/ubuntu/workspace/pset3/find/helpers.c:15: multiple definition of `search'
/tmp/find-5e19c1.o:/home/ubuntu/workspace/pset3/find/find.c:71: first defined here
/tmp/helpers-e977f1.o: In function `sort':
/home/ubuntu/workspace/pset3/find/helpers.c:24: multiple definition of `sort'
/tmp/find-5e19c1.o:/home/ubuntu/workspace/pset3/find/find.c:99: first defined here
clang: error: linker command failed with exit code 1 (use -v to see invocation)
make: *** [find] Error 1

//binary search
bool search (int target, int array[],int length)
{
int end =  length-1;
int start = 0;
while (start <=  end)
{
int middle  = (start + end)/2;
if (  target > array[middle] )
{
start = middle+1;
if (array[start] ==  target)
{
return true;
}
}
else if(target < array[middle])
{
end = middle - 1;
}
}
return false;
}

//bubble sort

void sort (int array[], int  total )
{
for (int min = 0; min < total - 1; min++)
{
for (int left = 0, right = left + 1; right < total - min; left++, right++)
{
if (array[left] > array[right])
{
//swap left and right element
int temp = array[left];
array[left] = array[right];
array[right] = temp;
}
}
}
}
``````