C++

Forum

 
Arrays, The Binary Search Algorithm

coolProgramer5 (193)
Hi I have to write a program that removes all duplicate values from a sorted array of integers, leaving only a single copy of each value. I'm almost done with the program however, I'm having problems checking the number for duplicates. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
 
#include <stdio.h>
#include "simpio.h"

void removedup (int inpArray[],  int inpArraySize, int outArray[], int arr[]);
int main()
{
    int size=5;
    int inpArray[size], inpArraySize, outArray[size], arr[size];
    removedup(inpArray, inpArraySize, outArray, arr);
    getchar();
    return 0;
}
void removedup (int inpArray[],  int inpArraySize, int outArray[], int arr[])
{
    int x, y, w=1;
    int z=0;
    printf("Enter the size of inpArray\n");
    inpArraySize=GetInteger();
    printf("Enter %d integers\n", inpArraySize);
    for (x=0; x<inpArraySize; x++)
    {
        inpArray[x]=GetInteger();
    }
    printf("These are the original values of 'inpArray[]=\n");
    for (x=0; x<inpArraySize; x++)
    {
        printf("%d ", inpArray[x]);
    }
    for (x=0; x<inpArraySize; x++)
    {
                         for (y=0; y<inpArraySize-1; y++)
                         {
                             if (y==inpArraySize-1 && x==y)
                             {
                                             break;
                                             break;
                             }
                             if (x==y && y<inpArraySize-1)
                             {
                                      y+=1;
                             }
                             if (inpArray[x] != inpArray[y])
                             {
                                             arr[z]=inpArray[x];
                                             z+=1;
                                             w+=1;
                             }
                         }
    }
    printf("\n\n");
    printf("In addition, these are the values of the new array without duplicates:\n"); 
    for (z=0; z<w; z+=1)
    {
        printf("%d ", outArray[z]);
    }
        
}
coolProgramer5 (193)
Please help.
n4nature (245)
You don't need a binary search to remove duplicates from a sorted array. Binary search is a Search algorithm. Here, you're not searching anything.

Here's an easier to understand program.

You can write a separate function to fill-in the input array and call this function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
int removeDup(int* a, int& size)
{
	for(int k=1; k<size; ++k)
	{
		if(a[k]==a[k-1])
		{
			for(int j=k; j<=size; ++j)
				a[j]=a[j+1];
			--size;
		}
		//here fill unique array, representing elements not having duplicates
	}
	return 0;
}
Last edited on
coolProgramer5 (193)
Ok I changed the program a little towards your example n4nature. However, in the output there are duplicates.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
#include <stdio.h>
#include "simpio.h"

int removedup (int inpArray[],  int inpArraySize, int outArray[], int arr[]);
int main()
{
    int size=5;
    int inpArray[size], inpArraySize, outArray[size], arr[size];
    removedup(inpArray, inpArraySize, outArray, arr);
    getchar();
    return 0;
}
int removedup (int inpArray[],  int inpArraySize, int outArray[], int arr[])
{
    int i, x, k;
    printf("Enter the size of inpArray\n");
    inpArraySize=GetInteger();
    printf("Enter %d integers\n", inpArraySize);
    for (x=0; x<inpArraySize; x++)
    {
        inpArray[x]=GetInteger();
    }
    printf("These are the original values of 'inpArray[]=\n");
    for (x=0; x<inpArraySize; x++)
    {
        printf("%d ", inpArray[x]);
    }
     printf("\n\n");
    printf("In addition, these are the values of the new array without duplicates:\n"); 
	for(int k=1; k<inpArraySize; k++)
	{
		if(inpArray[k]==inpArray[k-1])
		{
			for(int j=k; j<=inpArraySize; j++)
				inpArray[j]=inpArray[j+1];
			inpArraySize--;
		}
		 printf("%d ", inpArray[k]);
	}
	return 0;
}
n4nature (245)
Can you post the sample input and output?
coolProgramer5 (193)
sure.

input size = 8
input for 'inpArray[x]' = 1 2 1 4 3 5 7 3
output for 'outArray[k]' = 2 1 4 3 5 7 3
n4nature (245)
Didn't you mention in your program statement that the input array was supposed to be a sorted one, with duplicates?
coolProgramer5 (193)
Oh...Yes I am. I forgot about that.
n4nature (245)
Anyway, I do see a few things, as mentioned below:

Original snippet:
1
2
3
4
5
6
7
8
9
10
 
for(int k=1; k<inpArraySize; k++)
{
	if(inpArray[k]==inpArray[k-1])
	{
		for(int j=k; j<=inpArraySize; j++)
			inpArray[j]=inpArray[j+1];
		inpArraySize--;
	}
	 printf("%d ", inpArray[k]);
}


Modify it to:
1
2
3
4
5
6
7
8
9
10
 
for(int k=1; k<inpArraySize; k++)
{
	if(inpArray[k]==inpArray[k-1])
	{
		for(int j=k; j<inpArraySize; j++)
			inpArray[j]=inpArray[j+1];
		inpArraySize--;
	}
}
printf("%d ", inpArray[k]);
coolProgramer5 (193)
ok however, now the program crashes.. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
#include <stdio.h>
#include "simpio.h"

int removedup (int inpArray[],  int inpArraySize, int outArray[], int arr[]);
int main()
{
    int size=5;
    int inpArray[size], inpArraySize, outArray[size], arr[size];
    removedup(inpArray, inpArraySize, outArray, arr);
    getchar();
    return 0;
}
int removedup (int inpArray[],  int inpArraySize, int outArray[], int arr[])
{
    int i, x, k;
    printf("Enter the size of inpArray\n");
    inpArraySize=GetInteger();
    printf("Enter %d integers\n", inpArraySize);
    for (x=0; x<inpArraySize; x++)
    {
        inpArray[x]=GetInteger();
    }
    printf("These are the original values of 'inpArray[]=\n");
    for (x=0; x<inpArraySize; x++)
    {
        printf("%d ", inpArray[x]);
    }
     printf("\n\n");
    printf("In addition, these are the values of the new array without duplicates:\n"); 
	for(int k=1; k<inpArraySize; k++)
    {
	        if(inpArray[k]==inpArray[k-1])
	        {
		                                  for(int j=k; j<inpArraySize; j++)
			                              inpArray[j]=inpArray[j+1];
		                               inpArraySize--;
         }
    }
printf("%d ", inpArray[k]);


	return 0;
}
n4nature (245)
It was an uncomplied program. I had a chance to compile the program now.

This works for me:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
int removeDup(int* a, int& size)
{
	for(int k=1; k<size; ++k)
	{
		if(a[k]==a[k+1])
		{
			for(int j=k; j<size; ++j)
				a[j]=a[j+1];
			--size;
			--k;
		}
		//here fill unique array, representing elements not having duplicates
	}
	return 0;
}
Last edited on
coolProgramer5 (193)
Actually I almost figured program out. It's just not printing out anything out. (And thanks for reminding me about sorting the array).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
 
#include <stdio.h>
#include "simpio.h"

int removedup (int inpArray[],  int inpArraySize, int outArray[], int arr[]);
int main()
{
    int size=5;
    int inpArray[size], inpArraySize, outArray[size], arr[size];
    removedup(inpArray, inpArraySize, outArray, arr);
    getchar();
    return 0;
}
int removedup (int inpArray[],  int inpArraySize, int outArray[], int arr[])
{
    int j = 0;
    int x, k, i;
    int count = 0;
    int flag, temp;
    printf("Enter the size of inpArray\n");
    inpArraySize=GetInteger();
    printf("Enter %d integers\n", inpArraySize);
    for (x=0; x<inpArraySize; x++)
    {
        inpArray[x]=GetInteger();
    }
    for(i = 1; (i <= inpArraySize) && flag; i++)
     {
          flag = 0;
          for (j=0; j < (inpArraySize -1); j++)
         {
               if (inpArray[j+1] < inpArray[j])      // ascending order simply changes to <
              { 
                    temp = inpArray[j];             // swap elements
                    inpArray[j] = inpArray[j+1];
                    inpArray[j+1] = temp;
                    flag = 1;               // indicates that a swap occurred.
               }
          }
     }
    printf("These are the original values of 'inpArray[] sorted from least to greatest\n");
    for (x=0; x<inpArraySize; x++)
    {
        printf("%d ", inpArray[x]);
    }
     printf("\n\n");
    printf("In addition, these are the values of the new array without duplicates\n"); 
    for (x=0; x<inpArraySize; x++)
    {
        if (inpArray[x] != inpArray[x+1])
        {
                        outArray[j]=inpArray[x];
                        j+=1;
        }
    }
    j-=1;
	for (i=0; i<inpArraySize-j; i++)
	{
        printf("%d ", outArray[i]);
    }
	return 0;
}
coolProgramer5 (193)
I figured my program out. And thanks n4nature.
Topic archived. No new replies allowed.