Помогите исправить алгоритм нахождения значений, которые присутствуют в массиве А, но отсутствуют в массиве В
p.s сортировка пузырьком и двоичный поиск нужны по заданию
Он выводит значения, которые находятся и в A, и в B, но нужно только которые находятся в А
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;
namespace TEST
{
class Program
{
static int[] BubbleSort(int[] mas) //сортировка пузырьком, по заданию
{
int temp;
for (int i = 0; i < mas.Length; i++)
{
for (int j = i + 1; j < mas.Length; j++)
{
if (mas[i] > mas[j])
{
temp = mas[i];
mas[i] = mas[j];
mas[j] = temp;
}
}
}
return mas;
}
static void Main(string[] args) //двоичный поиск, по заданию
{
Stopwatch time = new Stopwatch();
Random Rnd = new Random();
int mas_size = 100, m, lowerBound, upperBound;
int[] a = new int[mas_size];
int[] b = new int[mas_size];
int[] c = new int[mas_size];
int last_zap = 0;
for (int j = 0; j < a.Length; j++)
{
a[j] = Rnd.Next(0, 100);
b[j] = Rnd.Next(0, 100);
}
time.Start();
a = BubbleSort(a);
b = BubbleSort(b);
for (int j = 0; j < a.Length - 1; j++)
{
lowerBound = 0;
upperBound = mas_size;
if (last_zap > 0)
{
if (c[last_zap - 1] == a[j])
continue;
}
while (last_zap < 100) //НАХОЖДЕНИЕ ЗНАЧЕНИЙ МАССИВА А, КОТОРЫХ НЕТ В МАССИВЕ Б
{
m = (lowerBound + upperBound) / 2;
if (m >= mas_size)
break;
if (a[j] < b[m])
upperBound = m - 1;
else if (a[j] > b[m])
lowerBound = m + 1;
else
{
c[last_zap] = b[m];
last_zap++;
break;
}
if (lowerBound > upperBound || m == 0)
break;
}
}
time.Stop(); //установить время работы программы, по заданию
Console.WriteLine("Продолжительность работы: " + time.Elapsed);
if (mas_size <= 100)
{
Console.WriteLine("");
for (int j = 0; j < a.Length; j++)
{
Console.Write("a[{0}] = {1};", j + 1, a[j]);
if (j % 10 == 9) Console.WriteLine();
}
Console.WriteLine();
for (int j = 0; j < b.Length; j++)
{
Console.Write("b[{0}] = {1};", j + 1, b[j]);
if (j % 10 == 9) Console.WriteLine();
}
if (last_zap > 0)
{
Console.Write("\n Элементы, которые присутствуют в массиве А, но отсутствуют в массиве В:\n");
for (int j = 0; j < last_zap; j++)
{
{ Console.Write(c[j] + " ");
}
}
else
Console.WriteLine("\n Не соответствуют условию\n");
}
Console.ReadLine();
}
}
}
Ответы (2 шт):
Автор решения: MBo
→ Ссылка
Выделите бинарный поиск в отдельную функцию. Возьмите такую его реализацию, которая возвращает индекс вставки элемента
Если на шарп перевести, будет примерно так:
//l == r == искомый индекс
//Если искомого элемента не было в массиве,
//бинарный поиск найдёт следующий после него элемент.
static int binsearch_array(int[] a, int val, int l, int r) {
while (r > l) {
int m = (l + r) / 2; //целочисленное деление!
if (a[m] < val) {
l = m + 1;
} else if (a[m] > val) {
r = m - 1;
} else {
return m;
}
}
return l;
}
Получив индекс, сравните значение с элементом по этому индексу. Если не равны, то значение отсутствует, и следующий бинарный поиск начинайте именно с этого индекса (при сортированном первом массиве).
Автор решения: Александр Гусев
→ Ссылка
using System;
using System.Collections.Generic;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;
namespace TEST
{
class Program
{
static int[] BubbleSort(int[] mas) //сортировка пузырьком
{
int temp;
for (int i = 0; i < mas.Length; i++)
{
for (int j = i + 1; j < mas.Length; j++)
{
if (mas[i] > mas[j])
{
temp = mas[i];
mas[i] = mas[j];
mas[j] = temp;
}
}
}
return mas;
}
static void Main(string[] args) //двоичный поиск, по заданию
{
Stopwatch time = new Stopwatch();
Random Rnd = new Random();
int mas_size = 10, m, lowerBound, upperBound;
int[] a = new int[mas_size];
int[] b = new int[mas_size];
int[] c = new int[mas_size];
int last_zap = 0;
for (int j = 0; j < a.Length; j++)
{
a[j] = Rnd.Next(0, 100);
b[j] = Rnd.Next(0, 100);
}
time.Start();
a = BubbleSort(a);
b = BubbleSort(b);
for (int j = 0; j < a.Length - 1; j++)
{
lowerBound = 0;
upperBound = mas_size;
if (last_zap > 0)
{
if (c[last_zap - 1] == a[j])
continue;
}
while (true) //проблемная часть
{
m = (lowerBound + upperBound) / 2;
if ((m < 0) || (m > mas_size - 1))
break;
if (a[j] < b[m])
upperBound = upperBound - 1;
else if (a[j] > b[m])
lowerBound = lowerBound + 1;
else
{
break;
}
if (lowerBound > upperBound || m == 0)
{
c[last_zap] = a[j];
last_zap++;
break;
}
}
}
time.Stop(); //установить время работы программы, по заданию
Console.WriteLine("Продолжительность работы: " + time.Elapsed);
if (mas_size <= 10)
{
Console.WriteLine("");
for (int j = 0; j < a.Length; j++)
{
Console.Write("a[{0}] = {1};", j + 1, a[j]);
if (j % 10 == 9) Console.WriteLine();
}
Console.WriteLine();
for (int j = 0; j < b.Length; j++)
{
Console.Write("b[{0}] = {1};", j + 1, b[j]);
if (j % 10 == 9) Console.WriteLine();
}
if (last_zap > 0)
{
Console.Write("\n Элементы, которые присутствуют в массиве А, но отсутствуют в массиве В:\n");
for (int j = 0; j < last_zap; j++)
{
if (c[j] != 0) { Console.Write(c[j] + " "); };
}
}
else
Console.WriteLine("\nНе соответствуют условию\n");
}
Console.ReadLine();
}
}
static void Main(string[] args) //двоичный поиск, по заданию
{
Stopwatch time = new Stopwatch();
Random Rnd = new Random();
int mas_size = 10, m, lowerBound, upperBound;
int[] a = new int[mas_size];
int[] b = new int[mas_size];
int[] c = new int[mas_size];
int last_zap = 0;
for (int j = 0; j < a.Length; j++)
{
a[j] = Rnd.Next(0, 100);
b[j] = Rnd.Next(0, 100);
}
time.Start();
a = BubbleSort(a);
b = BubbleSort(b);
for (int j = 0; j < a.Length - 1; j++)
{
lowerBound = 0;
upperBound = mas_size;
if (last_zap > 0)
{
if (c[last_zap - 1] == a[j])
continue;
}
while (true) //проблемная часть
{
m = (lowerBound + upperBound) / 2;
if ((m < 0) || (m > mas_size - 1))
break;
if (a[j] < b[m])
upperBound = upperBound - 1;
else if (a[j] > b[m])
lowerBound = lowerBound + 1;
else
{
break;
}
if (lowerBound > upperBound || m == 0)
{
c[last_zap] = a[j];
last_zap++;
break;
}
}
}
time.Stop(); //установить время работы программы, по заданию
Console.WriteLine("Продолжительность работы: " + time.Elapsed);
if (mas_size <= 10)
{
Console.WriteLine("");
for (int j = 0; j < a.Length; j++)
{
Console.Write("a[{0}] = {1};", j + 1, a[j]);
if (j % 10 == 9) Console.WriteLine();
}
Console.WriteLine();
for (int j = 0; j < b.Length; j++)
{
Console.Write("b[{0}] = {1};", j + 1, b[j]);
if (j % 10 == 9) Console.WriteLine();
}
if (last_zap > 0)
{
Console.Write("\n Элементы, которые присутствуют в массиве А, но отсутствуют в массиве В:\n");
for (int j = 0; j < last_zap; j++)
{
if (c[j] != 0) { Console.Write(c[j] + " "); };
}
}
else
Console.WriteLine("\nНе соответствуют условию\n");
}
Console.ReadLine();
}
}
}