AMCAT Automata Fix Sample Question-1

May 19, 2023

Program 1

BINARY SEARCH

Given function/method Search performs Binary Search and takes an vector of integers nums which is sorted in ascending order, and an integer target as input .The function/method Search searches target in nums. If target exists, then return its index. Otherwise, return -1.
The function/method Search is giving Time Limit Exceeded error. Your task is to fix the code so that it passes all the test cases.

Incorrect Code

Correct Code

Incorrect Code

int search (vector < int >&nums, int target)
{

  int start = 0;
  int end = nums.size () - 1;
  while (start <= end)
    {
      int mid = (end + start) / 2;
      if (target == nums[mid])
	return mid;

      else if (target <= nums[mid])
	end = mid + 1;

      else
	start = mid - 1;

    }
  return -1;

}

Correct Code

int search (vector < int >&nums, int target)
{

  int start = 0;
  int end = nums.size () - 1;
  while (start <= end)
    {
      int mid = (end + start) / 2;
      if (target == nums[mid])
	return mid;

      else if (target <= nums[mid])
	end = mid - 1;

      else
	start = mid + 1;

    }
  return -1;

}