BinarySearch Function

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

The most important thing is understand how Binary Search works.

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

mid = (first + last) / 2;

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

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

• 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[mid] < target)
{
    first = mid + 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
{
    last = mid - 1;
}

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

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

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

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

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