Реализация бинарного поиска в Java

Как вывести индексы элементов, которые находятся правее или левее центрального элемента? При вводе числа, которого нет в массиве, появляется индекс элемента, который = 3

package com.company;

    import java.util.Scanner;

    public class Main {
        private static int num; // элемент, индекс которого необходимо найти
        private static int k; // кол-во элементов массива
        private static int[] a;
        private static int i = 0;
        private static Scanner sc = new Scanner(System.in);

        public static void main(String[] args) {
            EnterArray();
            ShakerSortArray();
            BinarySearch();
        }

        public static void EnterArray() {

            System.out.print("Введите кол-во элементов: ");
            k = sc.nextInt();

            a = new int[k];
            System.out.print("Введите элементы массива: ");
            for (i = 0; i < k; i++) {
                a[i] = sc.nextInt();
            }
        }

        public static void ShakerSortArray() {
            int[] tmp;
            tmp = new int[k];

            int left = 0; // Левая граница
            int right = k - 1; // Правая граница (кол-во элементов -1)

            while (left <= right) {
                for (i = right; i > left; i--) {
                    if (a[i - 1] > a[i]) {
                        tmp[i] = a[i];
                        a[i] = a[i - 1];
                        a[i - 1] = tmp[i];
                    }
                }
                left++;
                for (i = left; i < right; i++) {
                    if (a[i] > a[i + 1]) {
                        tmp[i] = a[i + 1];
                        a[i + 1] = a[i];
                        a[i] = tmp[i];
                    }
                }
                right--;
            }
        }

        public static void BinarySearch() {
            int left = 0;
            int right = k;
            int mid = 0;

            System.out.print("Введите элемент, индекс которого хотите найти: ");
            num = sc.nextInt();

            while (left <= right) {
                mid = (left + right) / 2;
                if (a[mid] == num) {
                    i = mid;
                    break;
                } else if (num < a[mid]) {
                    right = mid - 1;
                } else if (num > a[mid]) {
                    left = mid + 1;
                }
                left++;
            }

            if (i == -1) {
                System.out.print("Элемента не существует");
            } else {
                System.out.print("Индекс введенного элемента равен: " + i);
            }
        }
    }