def verify(
        self,
        x: np.ndarray,
        y: np.ndarray,
        eps_init: float,
        norm: float = np.inf,
        nb_search_steps: int = 10,
        max_clique: int = 2,
        max_level: int = 2,
    ) -> tuple[float, float]:
        """
        Verify the robustness of the classifier on the dataset `(x, y)`.

        :param x: Feature data of shape `(nb_samples, nb_features)`.
        :param y: Labels, one-hot-encoded of shape `(nb_samples, nb_classes)` or indices of shape
                  (nb_samples,)`.
        :param eps_init: Attack budget for the first search step.
        :param norm: The norm to apply epsilon.
        :param nb_search_steps: The number of search steps.
        :param max_clique: The maximum number of nodes in a clique.
        :param max_level: The maximum number of clique search levels.
        :return: A tuple of the average robustness bound and the verification error at `eps`.
        """
        if np.min(x) < 0 or np.max(x) > 1:
            raise ValueError(
                "There are features not in the range [0, 1]. The current implementation only supports normalized input"
                "values in range [0 1]."
            )

        self.x: np.ndarray = x
        self.y: np.ndarray = check_and_transform_label_format(
            y, nb_classes=self._classifier.nb_classes, return_one_hot=False
        )
        self.max_clique: int = max_clique
        self.max_level: int = max_level

        average_bound: float = 0.0
        num_initial_successes: int = 0
        num_samples: int = x.shape[0]

        # pylint: disable=too-many-nested-blocks
        pbar = trange(num_samples, desc="Decision tree verification", disable=not self.verbose)
        for i_sample in pbar:

            eps: float = eps_init
            robust_log: list[bool] = []
            i_robust = None
            i_not_robust = None
            eps_robust: float = 0.0
            eps_not_robust: float = 0.0
            best_score: float | None

            for i_step in range(nb_search_steps):
                logger.info("Search step %d: eps = %.4g", i_step, eps)

                is_robust = True

                if self._classifier.nb_classes <= 2:
                    best_score = self._get_best_score(i_sample, eps, norm, target_label=None)
                    is_robust = (self.y[i_sample] < 0.5 and best_score < 0) or (
                        self.y[i_sample] > 0.5 and best_score > 0.0
                    )
                else:
                    for i_class in range(self._classifier.nb_classes):
                        if i_class != self.y[i_sample]:
                            best_score = self._get_best_score(i_sample, eps, norm, target_label=i_class)
                            is_robust = is_robust and (best_score > 0.0)
                            if not is_robust:
                                break

                robust_log.append(is_robust)

                if is_robust:
                    if i_step == 0:
                        num_initial_successes += 1
                    logger.info("Model is robust at eps = %.4g", eps)
                    i_robust = i_step
                    eps_robust = eps
                else:
                    logger.info("Model is not robust at eps = %.4g", eps)
                    i_not_robust = i_step
                    eps_not_robust = eps

                if i_robust is None:
                    eps /= 2.0
                else:
                    if i_not_robust is None:
                        if eps >= 1.0:  # pragma: no cover
                            logger.info("Abort binary search because eps increased above 1.0")
                            break
                        eps = min(eps * 2.0, 1.0)
                    else:
                        eps = (eps_robust + eps_not_robust) / 2.0

            if i_robust is not None:
                clique_bound = eps_robust
                average_bound += clique_bound
            else:
                logger.info(
                    "point %s: WARNING! no robust eps found, verification bound is set as 0 !",
                    i_sample,
                )

        verified_error = 1.0 - num_initial_successes / num_samples
        average_bound = average_bound / num_samples

        logger.info("The average interval bound is: %.4g", average_bound)
        logger.info("The verified error at eps = %.4g is: %.4g", eps_init, verified_error)

        return average_bound, verified_error

        Verify the robustness of the classifier on the dataset `(x, y)`.

        :param x: Feature data of shape `(nb_samples, nb_features)`.
        :param y: Labels, one-hot-encoded of shape `(nb_samples, nb_classes)` or indices of shape
                  (nb_samples,)`.
        :param eps_init: Attack budget for the first search step.
        :param norm: The norm to apply epsilon.
        :param nb_search_steps: The number of search steps.
        :param max_clique: The maximum number of nodes in a clique.
        :param max_level: The maximum number of clique search levels.
        :return: A tuple of the average robustness bound and the verification error at `eps`.
        
art/metrics/verification_decisions_trees.py