Алгоритмы - Двоичный поиск или Бинарный поиск или Алгоритм деления пополам.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class BinarySearchSample {

    public static void main(String[] args) throws IOException {
        
        System.out.println("Введите массив уникальных целых чисел (находит первое уникальное число):");
        
        ArrayList<Integer> arr = readIntegers();
        
        System.out.println("Введите искомое число:");
        
        Integer searchInteger = readInteger();
        
        // Сортируем начальный массив и так его храним.
        sortArrBuble(arr);
        
        System.out.println("Отсортированный массив:");
        printArr(arr);
        
        // Алгортм расчитан на уникальные целые, если оно не уникально то алгоритм не работает.
        Integer searchIndex = binarySearch(arr, searchInteger);
        
        if(searchIndex == null) {
            
            System.out.println("Искомое число не содержиться в массиве!");
            
        }
        else {
            
            System.out.println(String.format("Искомый индекс: %d. Нумерация от нуля.", searchIndex));
            
        }
        
        test();

        System.in.read();
    }
    

    private static Integer binarySearch(ArrayList<Integer> arr, Integer searchInteger) {
        
        // Переменная для хранения найденного индекса.
        Integer result = null;
        
        // Найдена ли переменная?
        boolean found = false;
        
        // exit == true при завершении поиска после обхода всего массива и не найдености искомого числа.
        boolean exit = false;
        
        // Анализируемая половина: false - левая, true - правая.
        boolean half = false;
        
        // Индекс верхней половины.
        int indexTop = (arr.size() - 1);
        
        // Индекс нижней половины.
        int indexBottom = 0;
        
        // Первая итерация?
        boolean firstIteration = true;

        while(!found && !exit) {
            
            if(firstIteration) {
                
                firstIteration = false;
                
            }
            else {
                if(half) {
                    indexBottom = (indexTop - indexBottom) / 2 + indexBottom + 1;
                }
                else {
                    indexTop = (indexTop - indexBottom) / 2 + indexBottom - 1;
                }
            }

            if(indexTop - indexBottom >= 0) {

                if(arr.get((indexTop - indexBottom) / 2 + indexBottom).intValue() == searchInteger.intValue()) {
                    
                    result = (indexTop - indexBottom) / 2 + indexBottom;
                    found = true;
                    
                }
                else {
                    
                    // Данный пример задан для сортировки от меньшего к большему:
                    if(arr.get((indexTop - indexBottom) / 2 + indexBottom).intValue() < searchInteger.intValue()) {
                        half = true;
                    }
                    else {
                        half = false;
                    }
                    
                }

            }
            else {
                
                exit = true;
                
            }
            
        }
        
        return result;
    }
    
    private static void test() {
        
        Integer testCount = 10000;
        
        ArrayList<Integer> arr = new ArrayList<Integer>(testCount);
        
        for(Integer i = 0; i < testCount; i++) arr.add(i);

        Integer failedTestNum = 0;
        
        for(Integer i = 128; i < testCount; i++) {
            
            Integer searchIndex = binarySearch(arr, i);
            
            if(searchIndex.intValue() != i.intValue())
                failedTestNum ++;
        }
        
        System.out.println("Алгоритм тестировался. Количество проваленных тестов: " + failedTestNum + ".");
    }

    private static void sortArrBuble(ArrayList<Integer> arr) {
        
        Integer temp;
        
        for(int i = 0; i <= arr.size() / 2; i++) {
            
            for(int j = 0; j < arr.size() - 1; j++) {
                
                if(arr.get(j) > arr.get(j + 1)) {
                    
                    temp = arr.get(j);
                    arr.set(j, arr.get(j + 1));
                    arr.set(j + 1, temp);
                
                }
            }
            
        }
        
    }
    
    private static void printArr(ArrayList<Integer> arr) {
        
        for(int i = 0; i < arr.size() - 1; i++) {
        
            System.out.print(arr.get(i) + " ");
            
        }
        
        System.out.print(arr.get(arr.size() - 1));
        
        System.out.println();
    }
    
    private static ArrayList<Integer> readIntegers() throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        ArrayList<Integer> result = new ArrayList<Integer>();
        
        String[] stringIntegers = br.readLine().split(" ");
        
        for(int i = 0; i < stringIntegers.length; i++) {
            
            result.add(Integer.parseInt(stringIntegers[i]));
            
        }

        return result;
    }
    
    private static Integer readInteger() throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        return Integer.parseInt(br.readLine());
    }
}