• запровадити поняття табличних величин (масивів) і опису їх мовою програмування Java;
• описати створення одно- та двовимірних масивів та виведення їх на консоль;
• описати створення багатовимірних масивів та виведення їх на консоль;
• ознайомитись з прикладами сортування масивів та роботи з масивами.

Обладнання: комп'ютери зі встановленими ОС та середовищем програму­вання мовою Java: JDK (Java Development Kit) + Eclipse.

Структура уроку

1. Організаційний момент.
2. Актуалізація опорних знань.
3. Інструктаж з ТБ.
4. Вивчення нового матеріалу.
5. Закріплення вивченого матеріалу.
6. Підбиття підсумків уроку.
7. Домашнє завдання.

• назва;
• стан — сукупність змінних;
• методи — операції.

3 групи типів даних мови Java:

• цілі числа — byte, short, int, long, char;
• числа з рухомою крапкою — float, double;
• логічні типи — boolean.

int aM;      // створили змінну aM   типу int
double chPI; // створили змінну chPI типу double

Алгоритм створення і виконання проекту Java в інтегрованому середовищі програму­вання Eclipse з викорис­танням контекс­ного меню.

3. Інструктаж з ТБ
4. Вивчення нового матеріалу

Необхідність запам’ятовувати, зберігати та використовувати великий набір однотипних даних (величин) привела до створення масивів (таблиць). Наприклад, масиви створюють у випадку потреби зберігати 30 різних імен і щоб для кожного імені не створювати окрему змінну.

Масив — згруповані за місцем розташування у пам'яті величини (всі або змінні, або сталі) одного типу, що мають одну назву (ідентифікатор) і різні порядкові номери (індекси). Це поняття програмування відповідає математичним поняттям послідовності, таблиці (матриці), тензора.

Елемент масиву — одна з величин, що утворюють масив. Це поняття програмування відповідає математичному поняттю елемента послідовності чи матриці.

Індекс масиву — величина перелічуваного (зазвичай цілого) типу, яка (сукупність яких) вказує на конкретний елемент масиву. Це поняття програмування відповідає математичному поняттю номера елемента послідовності чи номеру рядка/стовпчика таблиці (матриці).

Властивості масиву:

• тип елементів (масиву);
• назва (ідентифікатор) — одна й та сама для всіх елементів масиву;
• розмірність — кількість номерів (індексів), необхідних для визначення розташу­вання елемента у масиві;
• діапазони зміни номерів (індексів).

Примітка:

Cукупність розмірності й діапазонів зміни номерів індексів називають формою масиву.

Звернення до значення елемента масиву у коді програми здійснюють, вказавши після його назви у квадратних дужках індекси у вигляді (арифметичних) виразів, що набувають значень з діапазопу цілочисленного типу (int). Наприклад,
а[3] — 3-тій елемент масиву а,
с[j] — елемент масиву с з індексом j.

Елемент масиву може мати і тип простої (неструктурованої) величини і складений тип (масиву, рядка тощо), тобто може існувати масив масивів, масив рядків тощо. Глибину вкладеності (а значить, і кількість індексів) необмежено, але загальну довжину структури обмежено.

Найпростішими за формою є масиви розмірності 1 (лише один індекс). Такі масиви називають лінійними або одновимірними чи векторами.

Найменше значення індекса вектора дорівнює 0. Найбільше значення індекса лінійного масиву дорівнює довжині масиву, зменшеній на одиницю. У математиці лінійному масиву відповідає поняття послідовності, а індекс масиву — номеру члена послідовності.

Форми оголошення (опису) масиву

• або тип[] назва_змінної;
• або тип назва_змінної[];

Наприклад,

byte[]    anArrayOfBytes;
short[]   anArrayOfShorts;
int[]     anArrayOfInt;
long[]    anArrayOfLongs;
float[]   anArrayOfFloats;
double[]  anArrayOfDoubles;
boolean[] anArrayOfBooleans;
char[]    anArrayOfChars;
String[]  anArrayOfStrings;

або

byte    anArrayOfBytes[];
short   anArrayOfShorts[];
int     anArrayOfInt[];
long    anArrayOfLongs[];
float   anArrayOfFloats[];
double  anArrayOfDoubles[];
boolean anArrayOfBooleans[];
char    anArrayOfChars[];
String  anArrayOfStrings[];

Дужки [] вказують лише на те, що змінні розташовано у масиві,але власне масиви ще не існують. Для існування масиву потрібно зарезервувати (виділити) пам'ять за допомогою оператора new.

Загальна форма оператора new щодо одновимірних масивів має такий вигляд:

змінна_масиву = new тип[розмір];

Наприклад,

anArrayOfStrings = new String[9];

Лише після того, як описано масив і для нього зарезервовано пам'ять, можна звертатись до довільного елемента масиву.

Суміщення оголошення і виділення пам'яті для масиву можна здійснити таким чином:

тип назва_змінної[] = new тип[розмір];

Розглянемо приклад суміщення оголошення і виділення пам'яті для масиву з даними про кількість днів у кожному місяці і виведення на консоль кількості днів у квітні.

package work;
public class Work {
  public static void main(String args[]) {
    int[] month_days;        // Оголошення масиву
    month_days = new int[12];// Резервування пам'яті для масиву з 12 елементів
    month_days[0] = 31;
    month_days[1] = 28;
    month_days[2] = 31;
    month_days[3] = 30;
    month_days[4] = 31;
    month_days[5] = 30;
    month_days[6] = 31;
    month_days[7] = 31;
    month_days[8] = 30;
    month_days[9] = 31;
    month_days[10] = 30;
    month_days[11] = 31;
    // Виведення на консоль
    System.out.println("У квітні "+month_days[3]+" днів.");
  }
}

У результаті роботи програми на екран буде виведено таке повідомлення:

У квітні 30 днів.

У Java нумерація елементів масиву починається з 0, тому квітню — четвертому місяцю року — відповідає елемент масиву month_days[3] з індексом 3.

Система Java виконує ретельну перевірку того, чи не була випадково здійснено спробу виходу за межі допустимого діапазону значень індексів масиву. Наприклад, у поданій програмі система часу виконання буде перевіряти відповідність значення кожного індексу допустимому діапазону від 0 до 11 включно. Якщо буде спроба звертання до елементів за межами цього діапазону, то це призведе до помилки виконання.

У Java всі значення масиву ініціалізують — заповнюють комірки пам'яті на початку виконання програми — певними значеннями як усталено для відповідних типів:

• byte, short, int, long, char — 0;
• float, double — 0.0;
• boolean — false;
• об’єкти — null.

Для успішної роботи з масивами потрібно уміти здійснювати щонайменше такі (базові) операції при роботі з масивами:

• ініціалізація масиву;
• введення та виведення масиву;
• копіювання масиву;
• пошук найбільшого чи найменшого елемента;
• обчислення функцій від елементів: суми, добутку тощо;
• пошук елементів з певними властивостями;
• обмін значеннями між елементами масиву;
• вставлення й видалення елемента.

Робота з багатовимірними масивами подібна до роботи з одновимірними. Відмінність лише в тому, що використовують додаткові квадратні дужки для додаткових індексів. Переважно використовуються двовимірні масиви для подання прямокутних таблиць даних. Наприклад, двовимірний і тривимірний масиви можна створити таким чином:

int twoD[][]     = new int[3][4];    //створення масиву 3x4
int threeD[][][] = new int[3][4][5]; //створення масиву 3х4х5

Двовимірний масив можна уявити у вигляді прямокутника, розділеного на квадрати-елементи. У цьому випадку перший індекс, записаний ліворуч, тлумачать як номер рядка, а другий індекс, записаний праворуч як номер — стовпчика. Це можна зобразити умовно таким чином:

[0,0][0,1][0,2][0,3][0,4]
[1,0][1,1][1,2][1,3][1,4]
[2,0][2,1][2,2][2,3][2,4]
[3,0][3,1][3,2][3,3][3,4]

Тривимірний масив можна уявити у вигляді прямокутного паралеле­піпеда, розділе­ного на куби-елементи.

Способи заповнення масиву

1. З клавіатури за допомогою класу Scanner з пакету java.util. Для отримання консольного введення в класі System визначено об’єкт in. З об’єктом System.in не дуже зручно працювати, тому, як правило, використовують клас Scanner, який у свою чергу використовує System.in — див. наступний приклад.

   package work;
   import java.util.Scanner;
   public class Work {
     public static void main(String[] args) {
       Scanner input = new Scanner(System.in);
       System.out.println("Input array length: ");
       int size = input.nextInt();  // Зчитування розміру масиву у змінну size
       int array[] = new int[size]; // Створення масиву array розміру size
       System.out.println("Input array elements:");
       for (int i = 0; i < size; i++) {
         array[i] = input.nextInt(); // Заповнення масиву
         }
       System.out.print ("Inserted array elements:");
       for (int i = 0; i < size; i++) {
         System.out.print (" " + array[i]); // Виведення введених раніше значень 
         }
       System.out.println();
       }
   }

   Спочатку імпортують клас Scanner з пакету java.util. Для створення самого об'єкта Scanner у його конструктор передають об'єкт System.in. Після цього можна отримувати значення, які вводять з клавіатури. Наприклад, щоб отримати введене число, використовують метод in.nextInt(), який повертає введене з клавіатури цілочисельне значення. В даному випадку в циклі вводяться всі елементи масиву, а за допомогою іншого циклу всі раніше введені елементи масиву виводяться в рядок.
   
   Клас Scanner має ще кілька методів, які дозволяють отримати введені користу­вачем значення:

   • next() — зчитує введений рядок до першого пробілу;
   • nextLine() — зчитує весь введений рядок;
   • nextInt() — зчитує введене число int;
   • nextDouble() — зчитує введене число double;
   • hasNext() — перевіряє, чи було введене слово;
   • hasNextInt() — перевіряє, чи було введено число int;
   • hasNextDouble() — перевіряє, чи було введено double.

   Методи nextByte / nextShort / nextFloat / nextBoolean класу Scanner за аналогією з nextInt зчитують дані відповідного типу даних.

2. З файлу. Для того, щоб ввести масив з файлу, потрібно запозичити необхідні складові з бібліотеки Java — див. перші рядки поданого далі коду, у якому є звертання до попередньо створеного текстового файлу input_array.txt. Цей файл має містити (у вказаному порядку) кількість елементів масиву та значення елементів цього масиву у порядку зростання номеру елемента.

   package work;
   import java.io.File;
   import java.io.FileNotFoundException;
   import java.util.Arrays;
   import java.util.Scanner;
   public class Work {
     public static void main(String[] args) throws FileNotFoundException {
       Scanner scanner = new Scanner(new File("input_array.txt"));
       int size = scanner.nextInt();
       int[] array = new int[size];
       for (int i = 0; i < size; i++) {
         array[i] = scanner.nextInt();
       }
       scanner.close();
       System.out.println("Array: " + Arrays.toString(array));
     }
   }

3. За допомогою методу fill для заповнення всього масиву однаковими значеннями.

   package work;
   import java.util.Arrays;
   public class Work {
     public static void main(String args[]) {
       int a[] = new int[5];
       Arrays.fill(a, 5);
       for (int i = 0; i < 5; i++) {
         System.out.print("a[" + i + "]=" + a[i] + "; ");
       }
     }
   }

4. З використанням генератора випадкових чисел Random з двома різними способами ініціалізації:

   • з використанням системих дати й часу (як усталено);
   • з використанням заданого числа типу long.

   При використанні останнього способу зі сталим числом кожного разу буде породжено однакові випадкові значення, тому на практиці в основному застосо­вують саме перший спосіб.
   
   Методи класу Random:

   • nextBoolean();
   • nextInt();
   • nextLong();
   • nextFloat();
   • nextDouble();

   Останні два методи породжують числа з рухомою крапкою лише з проміжку [0; 1], а цілочисельні — з усього діапазону значень. Але цілі числа можна породжувати і з діапазону від 0 до max – 1 включно (при певному натуральному max), якщо писати так: nextInt(max).

   package work;
   import java.util.Random;
   public class Work {
     public static void main(String args[]) {
       Random r = new Random();
       int[] a = new int[10];
       for (int i = 0; i < a.length; i++) {
         a[i] = r.nextInt(9);
         System.out.println("a["+i+"]="+a[i]);
       }
     }
   }

Дані, породжені випадковим чином, часто допомагають при тестуванні програм. Наприклад, для того, щоб перевірити правильність впорядкування послідовності чисел.

Приклад 1 — знаходження найбільший елемент лінійного масиву.

package work;
public class Work {
  public static void main(String[] args) {
    double array[] = {1.1, 2.2, 1.1, 3.2, 1.2, 2.1};
    double max = array[0];
    for (int i = 0; i < 6; i++) {
      if (max < array[i]) {
        max = array[i];
      }
    }
    System.out.println ("Найбільше число у масиві: " + max);
  }
}

Cпочатку змінній max надано значення елементу масиву з індексом 0, після чого (в циклі) йде послідовне порівняння max з кожним наступним елементом масиву числом до останнього. Якщо при порівнянні значення чергового значення у масиві більше за значення max, то змінній max буде надано це значення. По закінченню циклу змінна max міститиметься максимальне значення, яке і буде виведене на консоль:

Найбільше число у масиві: 3.2

У Java масиви є спеціальними об’єктами, що забезпечує деяку додаткову функціональність масивам. Зокрема, можна дізнатися довжину масиву за допомогою методу length. Для поданого вище прикладу можна замінити рядок з циклом таким чином:

for (int i = 0; i < array.length; i++) {

Приклад 2 — обчислення суми значень елементів масиву

package work;
public class Work {
  public static void main(String args[]) {
    int nums[] = {10, 11, 12, 13, 14};
    int result = 0;
    for (int i = 0; i < nums.length; i++) {
      result = result + nums[i];
    }
    System.out.println("Cума значень елементів масиву дорівнює " + result);
  }
}

У результаті на консоль буде виведено таке повідомлення:

Cума значень елементів масиву дорівнює 60

Приклад 3 — обчислення середнього арифметичного значень елементів масиву

package work;
public class Work {
  public static void main(String args[]) {
    double nums[] = { 10.1, 11.2, 12.3, 13.4, 14.5 };
    double result = 0;
    for (int i = 0; i < nums.length; i++) {
      result = result + nums[i];
    }
    System.out.println("Середнє значення дорівнює " + result / 5);
  }
}

У результаті на консоль буде виведено таке повідомлення:

Середнє значення дорівнює 12.299999999999999

Приклад 4 — об’єднання (склеювання) масивів (фрагмент програми)

public static double[] concatArray(double[] a, double[] b) {
  double[] r = new double[a.length + b.length];
  System.arraycopy(a, 0, r, 0, a.length);
  System.arraycopy(b, 0, r, a.length, b.length);
  return r;
}

Тут замість типу double можна використати довільний інший тип.

Cортування (лінійного масиву) — упорядкування елементів масиву у порядку зростання чи спадання їхніх значень.

Це найпоширеніше завдання при роботі з лінійними масивами. Існує велика кількість різних алгоритмів, призначених для розв'язання цього завдання: метод бульбашки, вибором найбільшого (найменшого) значення, шейкерний, злиттям, вставки, пірамідальний, швидким методом Гоара. Всі методи різняться швидкістю виконання і потрібним об'ємом пам'яті, необхідної для зберігання проміжних даних і результатів. Далі подано описи деяких із них разом з програмною реалізацією мовою Java із випадковим заповненням масиву.

Метод сортування бульбашкою (Bubble sort)
Алгоритм проходить масив від початку і до кінця, порівнюючи попарно сусідні елементи, для яких різниця значень індексів дорівнює 1. Значення елементів розташовано у неправильному порядку, то їх міняють місцями, таким чином, після першого проходу на кінці масиву буде розташовано найбільший елемент (для упорядкування за зростанням). Тобто, найбільший елемент «спливе» до потрібної позиції як бульбашка у воді. Потім прохід масиву повторюють, і на передостанньому місці буде розташовано найбільший після максимального елемент і т.д.

package work;
import java.util.Arrays;
import java.util.Random;
public class Work {
  public static void main(String args[]) {
    int[] array = new int[10];
    Random random = new Random();
    for (int i = 0; i < array.length; i++) {
      array[i] = random.nextInt(30);
    }
    System.out.println("Array:");
    System.out.println(Arrays.toString(array));

    bubbleSort(array);
    System.out.println("Sorted array:");
    System.out.println(Arrays.toString(array));
  }

  public static void bubbleSort(int[] arr) {
    for (int i = arr.length - 1; i > 0; i--) {
      for (int j = 0; j < i; j++) {
        if (arr[j] > arr[j + 1]) {
          int tmp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = tmp;
        }
      }
    }
  }
}

Сортування вибором (Selection sort)
Змінюючи i від 0 — найменшого значення індексу — до (n – 1) — найбільшого значення індексу (n — кількість елементів масиву, яку називають довжиною масиву), робимо таке:

• визначаємо номер min_i найменшого елемента для індексів у межах від i до n – 1 включно;

• міняємо місцями значення елементів з індексами i та min_i. У результаті такої заміни на місце з номером (індексом) i стане потрібне значення.

Тут червоним тлом виділено те значення, яке серед елементів з номером від j до n вважають найменшим у поточний момент виконання алгоритму, блакитним — значення поточного елемента масиву, яке порівнюють з тим, що наразі вважають найменшим, жовтим — ті значення, які вже стоять на потрібному місці.

package work;
import java.util.Arrays;
import java.util.Random;
public class Work {

  public static void main(String args[]) {
    int[] array = new int[20];
    Random random = new Random();
    for (int i = 0; i < array.length; i++) {
      array[i] = random.nextInt(30);
    }
    System.out.println("Array:");
    System.out.println(Arrays.toString(array));

    selectionSort(array);
    System.out.println("Sorted array:");
    System.out.println(Arrays.toString(array));
  }

  public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
      int min = arr[i];
      int min_i = i;
      for (int j = i + 1; j < arr.length; j++) {
        if (arr[j] < min) {
          min = arr[j];
          min_i = j;
        }
      }
      if (i != min_i) {
        int tmp = arr[i];
        arr[i] = arr[min_i];
        arr[min_i] = tmp;
      }
    }
  }
}

Вище подано алгоритм вибору найменшого елемента при упорядкуванні за зростанням. Можливі й інші варіанти:

• вибір найменшого елемента при упорядкуванні за спаданням;
• вибір найбільшого елемента при упорядкуванні за зростанням;
• вибір найбільшого елемента при упорядкуванні за спаданням;

Метод швидкого сортування
Основу цього алгоритму розробив у 1962 році британський учений Чарлз Ентоні Річард Гоар (Charles Antony Richard Hoare). Рекурсивний алгоритм для впорядкування за неспаданням масиву зі значеннями індексів від l до r включно має такий вигляд:

1. Вибрати значення елемента масиву.

2. Значення елементів масиву, що не менші за вибране, розташувати на місцях з номерами (індексами) більшими від індексу обраного значення, а ті, що не перевищують — на місцях з номерами меншими від індексу обраного значення. У результаті вибране значення матиме той номер j у масиві, що потрібно. Тому надалі відповідний елемент масиву буде незмінним.

3. Якщо l < (j – 1), виконати алгоритм для індексів від l до (j – 1) включно.

4. Якщо (j + 1) < r, виконати алгоритм для індексів від (j + 1) до r включно.

Рекурсивність алгоритму означає виклик цього алгоритму в ньому самому — див. кроки 3–4. На малюнку нижче подано частину схеми впорядкування.

Тут кольоровими кругами позначено вибрані значення елементів масиву. Після переставлянь навколо них ці значення надалі залишаються нерухомими у масиві. Спочатку буде впорядковано ті елементи, які менші від значення, позначеного зеленим кольором, потім — менші від значення, позначеного червоним кольором, ще пізніше — менші від значення, позначеного синім кольором.

Примітка. Поданий вище запис стане алгоритмом лише після того, як буде деталізовано вибір значення. У багатьох описах алгоритму можна зустріти вибір елемента з найменшим чи з найбільшим номером. Розглянемо спробу впорядкувати вже впорядкований масив при такому виборі. Глибина занурення — кількість послідовних викликів рекурсивного алгоритму без виходу з нього — буде майже збігатися з довжиною масиву. Останнє може призвести до переповнення стеку частини оперативної пам'яті, куди програма заносить дані про виклик програми та функцій, їхні аргументи, точку повернення тощо. А переповнення стеку означає аварійне завершення роботи. Який би не був детерміністичний (без випадковостей) вибір значення (наприклад, із середини масиву), завжди можна вказати вхідні дані, для яких глибина занурення для цих вхідних даних лише на 1 відрізнятиметься від довжини масиву. Тому вибір потрібно робити з використанням генератора випадкових чисел. І в цьому випадку можливе переповнення стеку, але ймовірність цієї події настільки мала, що аварійне припинення роботи зазвичай не відбувається.

Проаналізуйте на відповідність опису ілюстрацію для вибору правого краю (елемента з найбільшим номером), запозичену із сайту http://uk.wikipedia.org/wiki

package work;
import java.util.Arrays;
import java.util.Random;
public class Work {

  private static final Random random = new Random();

  public static void main(String args[]) {
    int[] array = new int[20];
    for (int i = 0; i < array.length; i++) {
      array[i] = random.nextInt(30);
    }
    System.out.println("Array:");
    System.out.println(Arrays.toString(array));

    quickSort(array, 0, array.length - 1);
    System.out.println("Sorted array:");
    System.out.println(Arrays.toString(array));
  }

  public static void quickSort(int[] arr, int first, int last) {
    int i = first;
    int j = last;
    int x = arr[first + random.nextInt(last - first + 1)];
    do {
      while (arr[i] < x) {
        i++;
      }
      while (arr[j] > x) {
        j--;
      }
      if (i <= j) {
        if (arr[i] > arr[j]) {
          int temp = arr[i];
          arr[i] = arr[j];
          arr[j] = temp;
        }
        i++;
        j--;
      }
    } while (i <= j);
    if (i < last) {
      quickSort(arr, i, last);
    }
    if (first < j) {
      quickSort(arr, first, j);
    }
  }
}

Метод sort() з класу Arrays використовує вдосконалений алгоритм швидкого сортування за зростанням. Попередньо потрібно імпортувати java.util.Arrays. Після цього власне упорядкування записують одним рядком програми:

Arrays.sort(назва масиву);

У поданій нижче програмі використано також метод для виведення масиву — перетворення в рядок за допомогою Arrays.toString().

package work;
import java.util.Arrays;
public class Work {

  public static void main(String args[]) {
    int[] arr = { 4, 1, 2, 3, 5 };
    System.out.println("Array before sort");
    System.out.println(Arrays.toString(arr));
    Arrays.sort(arr);
    System.out.println("Array after sort:");
    System.out.println(Arrays.toString(arr));
  }
}

Результат виконання програми на екрані монітора матиме такий вигляд:

Array before sort
[4, 1, 2, 3, 5]

Array after sort:
[1, 2, 3, 4, 5]

Якщо елементи масиву — представника класу Arrays — є не числами, а об'єктами складнішої будови, потрібно переозначити відношення порівняння за допомогою інтерфесу Comparator — див. приклад коду

package work;
import java.util.*;
class A implements Comparator<A>, Comparable<A>
{ String s;
  int n;
  public A() { }
  public A (String s, int n)
  { this.s = s;
    this.n = n;
  }
  @Override public int compare (A a1, A a2){return a1.n - a2.n;}
  @Override public int compareTo (A a)     {return(this.s).compareTo(a.s);}
}
public class Work
{ public static void main(String[] args)
  { A[] a = {new A("b", 8), 
             new A("c", 6),
             new A("a", 7)};
    Arrays.sort(a);
    for (A a1 : a) System.out.println(a1.s + " " + a1.n);
    System.out.println();
    Arrays.sort(a, new A());
    for (A a1 : a) System.out.println(a1.s + " " + a1.n);   
  }
}

a 7
b 8
c 6

c 6
a 7
b 8

Метод обліку передбачає використання окремого масиву з нульовими початковими значеннями, який після перегляду масиву, що підлягає впорядкуванню, містить інформацію про те, скільки є елементів, що мають певне значення.

package work;
import java.util.Arrays;
import java.util.Random;
public class Work {

  public static void main(String args[]) {
    int max = 100;
    int[] arr = new int[20];
    Random random = new Random();
    for (int i = 0; i < arr.length; i++) {
      arr[i] = random.nextInt(max);
    }
    System.out.println("Array:");
    System.out.println(Arrays.toString(arr));

    countingSort(arr, max);
    System.out.println("Sorted array:");
    System.out.println(Arrays.toString(arr));
  }

  public static void countingSort(int[] arr, int max) {
    int[] countingArray = new int[max];
    for (int i = 0; i < arr.length; i++) {
      countingArray[arr[i]]++;
    }
    int l = 0;
    for (int i = 0; i < countingArray.length; i++) {
      for (int j = 0; j < countingArray[i]; j++) {
        arr[l] = i;
        l++;
      }
    }
  }
}

Алгоритм двійкового (бінарного) пошуку використовують для пошуку (індекса) елемента масиву з певним значенням. Цей алгоритм застосовують до попередньо упорядкованого лінійного масиву при розташуванні заданого значення елемента між найбільшим та найменшим значеннями елементів масиву. За рахунок упорядкованості масиву досягають великої швидкості пошуку — кількість операцій пропорційна log₂ N, що позначають таким чином: O(log₂ N).

Головна ідея двійкового пошуку — з кожним наближенням поділяти множину значень (приблизно) навпіл.

Для стислого опису алгоритму запровадимо такі позначення для змінних, початкові значення яких задають на початку виконання алгоритму:

• a — задане значення;
• a_j — значення елемента масиву з номером j;
• j_min — найменше зі значень номерів елементів масиву, серед яких здійснюють пошук;
• j_max — найбільше зі значень номерів елементів масиву, серед яких здійснюють пошук.

1. Поки j_min ≤ j_max робити таке:
   1. Обчислити значення j = [( j_min + j_max) / 2].
   2. Якщо a = a_j, то припинити виконання алгоритму з отриманим значенням j.
   3. Якщо a < a_j, то надати змінній j_max значення j – 1.
   4. Якщо a_j < a, то надати змінній j_min значення j + 1.

2. Повернути від'ємне значення – 1 як ознаку того, що шуканого індексу немає.

package work;
import java.util.Arrays;
import java.util.Random;
class Work
{ public static void main(String args[]) 
  { Random r = new Random();
    int j, n = 15, // кількість елементів
          da = 5;  // верхня межа приросту значень елементів
    int[]  a = new int[n];
    a[0]=0;
    for (j=1; j<n; j++) a[j] = a[j-1]+1+r.nextInt(da);
    System.out.println("Мвсив: " + Arrays.toString(a));
    int b = r.nextInt(a[n-1]+1); // число для розташування серед елементів масиву 
    System.out.print("\nЗначення "+b);
    j = binarySearch(a, b);
    if (j<0) System.out.println(" немає серед елементів масиву.");
    else     System.out.println(" має індекс "+j);
  }

  public static int binarySearch(int[] a, int b)
  { int j_min = 0;
    int j_max = a.length - 1;
    while (j_min <= j_max)
    { int j = (j_max + j_min) / 2;
      int c = a[j];
      if (c == b) return j;      else
      if (c <  b) j_min = j + 1;
      else        j_max = j - 1;
    }
    return -1;
  }
}

В Java є вбудований метод бінарного пошуку (binarySearch) у класі Arrays. При його використанні програма стане коротшою.

package work;
import java.util.Arrays;
import java.util.Random;
class Work
{ public static void main(String args[]) 
  { Random r = new Random();
    int j, n = 15, // кількість елементів
          da = 5;  // верхня межа приросту значень елементів
    int[]  a = new int[n];
    a[0]=0;
    for (j=1; j<n; j++) a[j] = a[j-1]+1+r.nextInt(da);
    System.out.println("Мвсив: " + Arrays.toString(a));
    int b = r.nextInt(a[n-1]+1); // число для розташування серед елементів масиву 
    System.out.print("\nЗначення "+b);
    j = Arrays.binarySearch(a, b);
    if (j<0) System.out.println(" немає серед елементів масиву.");
    else     System.out.println(" має індекс "+j);
  }
}

1. Що таке масив?
2. Які властивості має масив?
3. Що таке форма масиву?
4. Як описують масив мовою Java?
5. Які методи впорядкування лінійних масивів Ви знаєте?
6. У чому полягає впорядкування масиву швидким методом Хоара?
7. У чому полягає бінарний пошук?

6. Підбиття підсумків уроку
Виставлення оцінок.

7. Домашнє завдання

1. Вивчити матеріал уроку.

2. Написати програму розв'язання такої задачі: заповнити лінійний масив випадковим чином і визначити, скільки разів досягається найбільше значення у даному масиві та найменший порядковий номер (індекс) для такого найбільшого значення.

Текст упорядкувала Остапенко Галина Іванівна, вчитель Вищого мистецького коледжу «Київська дитяча Академія мистецтв» Оболонського району міста Києва, під час виконання випускної роботи на курсах підвищення кваліфікації з 24.10.2016 по 28.10.2016.