Bisection search doesnt return the correct index

Question

I want to search the index of a given integer within an array. The code does its job if the numbers in the given array don't repeat themselves, for example, if we are searching for the index of the integer 2 in int [] array = new int [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], but if the given array is, for example, int [] array = new int [1, 2, 2, 4, 5, 6, 7, 8, 9, 10, 11], the code will return the index 2, instead of 1.

public static int Bisection(int[] array, int element)
{
    int left = 0;
    int right = array.Length - 1;
    int middle = (left + right) / 2;

    while (array[middle] != element)
    {
        if (array[middle] < element)
        {
            left = middle + 1;
        }
        else
        {
            right = middle - 1;
        }
        middle = (left + right) / 2;


        if (right < left)
        {
            return -1;
        }
    }
    return middle;
}

So my question is, what should I do to return the lowest index of an integer if there are multiple integers in the array that are the same?

Answer 1

Check this:

public static int Bisection(int[] array, int element)
{
    int left = 0;
    int right = array.Length - 1;
    int middle = (left + right) / 2;

    while (array[middle] != element || (middle > 0 && array[middle - 1] == element))
    {
        if (array[middle] < element)
        {
            left = middle + 1;
        }
        else
        {
            right = middle - 1;
        }
        middle = (left + right) / 2;


        if (right < left)
        {
            return -1;
        }
    }
    return middle;
}

while condition is changed.