Recursive Binary Search does not find the element at the last vector position

Question

I made a recursive binary search code in Java. It finds the positions correctly, except when the searched element occupies the last position of the vector. I don’t know how to fix this.

public static int binarySearchRecursivo(int array[],int x) {
        return BinarySearchRec(array, x, 0, array.length-1);
        }
    
        public static int BinarySearchRec(int array[], int x, int inicio, int fim) {
         int meio = (inicio+fim)/2;
         if (inicio <= fim) {
             
         if (array[meio]==x) {
             return meio;
         }
         if (array[meio]<x) {
             return BinarySearchRec(array, x, meio+1, fim);
         }
         else {
             return BinarySearchRec(array, x, inicio, meio-1);
         }
         }
         return -1;
        }
    
    // Driver method to test above
    public static void main(String args[]) {
        
        int arr[] = {2,3,5,6,7,9,12,33,66,55};
        int x = 55;
        int result = binarySearchRecursivo(arr,x);
        if (result ==-1)
            System.out.println("Elemento não está presente");
        else
            System.out.println("Elemento encontrado na posição " + result);
    }
}

Answer 1

In a binary search, one of the prerequisites is that all elements are in order, otherwise nay there is no guarantee that will work.

In your case, the array is not ordered, because the penultimate element (66) is larger than the last (55).

If the array is ordered, then it works:

// trocando o 55 e 66 de posição, agora o array está ordenado
int arr[] = { 2, 3, 5, 6, 7, 9, 12, 33, 55, 66 };
int x = 66;
// restante do código igual, 66 é encontrado