BinarySearchRotated Function

The input parameters of the function are array and target value to find.

The most important thing is understand how Binary Search Rotated works.

• Get first and last index of array.
• Divided by two in the middle.

middle = (first + last) / 2;

• If the value is same as middle index, return the index.

if (input[middle] == target)
    return middle;

• If the value is greater than value in middle index, these middle index assigned to be first index.
  • Then, it starts again from calculating middle index.

if (input[first] <= target && target < input[middle])
{
    last = middle - 1;
}

• If the value is smaller than value in middle index, these middle index assigned to be last index.
  • Then, it starts again from calculating middle index.

else if (input[middle] < target && target <= input[last])
{
    first = middle + 1;
}

• If no condition matched, it automatically search from middle to end.

else
    first = middle - 1;

• It keeps looping until the target found or return -1 means no target in array.

static int binarySearchRotated(int[] input, int target)
{
    int first = 0;
    int last = input.Length - 1;
    int middle = 0;

    while (first <= last)
    {
        middle = (first + last) / 2;

        if (input[middle] == target)
            return middle;

        if (input[first] <= target && target < input[middle])
        {
            last = middle - 1;
        }
        else if (input[middle] < target && target <= input[last])
        {
            first = middle + 1;
        }
        else
            first = middle - 1;
    }
    return -1;
}