Untitled

package ru.yandex.programmers_day;


public class ProgrammersDayApplication {

	private static final char[] CHARACTERS = "0123456789ABCDEFabcdef".toCharArray();

	public static void main(String[] args) {
		String target = "abcd1111"; // Искомая строка
		String result = guessString(target);

		if (result != null) {
			System.out.println("Искомая строка: " + result);
		} else {
			System.out.println("Искомая строка не найдена.");
		}
	}

	public static String guessString(String target) {
		int length = target.length();
		char[] guess = new char[length];

		int low = 0;
		int high = CHARACTERS.length - 1;

		while (low <= high) {
			int mid = low + (high - low) / 2;
			
			guess[0] = CHARACTERS[mid];
			
			boolean found = binaryGuess(target, guess, 0);
			//тут делаем запрос и узнаем знак
			if (found) {
				return String.valueOf(guess);
			} else if (target.compareTo(String.valueOf(guess)) < 0) {
				high = mid - 1;
			} else {
				low = mid + 1;
			}
		}

		return null;
	}

	private static boolean binaryGuess(String target, char[] guess, int pos) {
		if (pos == guess.length - 1) {
			return target.equals(String.valueOf(guess));
		}

		int low = 0;
		int high = CHARACTERS.length - 1;

		while (low <= high) {
			int mid = low + (high - low) / 2;

			guess[pos + 1] = CHARACTERS[mid];

			if (binaryGuess(target, guess, pos + 1)) {
				return true;
			} else if (target.compareTo(String.valueOf(guess)) < 0) {
				high = mid - 1;
			} else {
				low = mid + 1;
			}
		}

		return false;
	}
}