CareerCup

1. Generally in BinarySearch algorithm we do 2 comparisions

while(stat < end )
{
  if( A[mid == KeyElem )
  {
     -----
  }
  else if( A[mid] < KeyElem )
  {
     ------
  }
  else
  {
      ----
  }
 ------
}// end of While

2. He asked me to use single comparision in While loop .

3. code for this .

int BinSearch(int A[], int n , int key )
{
	if( n <= 0 )
	{
		return -1; // key not found
	}
	else
	{
		int start = 0 ;
		int end = n - 1;
		int mid;
		
		while(start < end)
		{
			mid = (start + end) / 2 ;
			if( A[mid] > key )
			{
				start = mid + 1;
			}	
			else
			{
				end = mid ;
			}
		}
		if( ( start == end ) && ( A[start] == key ))
		{
			return start;
		}
		else
		{
			return -1; // key not found
		}
	}
}

Here is the Single Comparision Code:

int BinSearch(int A[], int n , int key )
{
	int s = 0;
	int e = n-1;
	int m;
	
	while(s<e)
	{
		m = (s+e)/2;
		if(key<=A[m])
		{
			e = m;
		}
		else
		{
			s = m+1;
		}
	}
	if(A[e] == key)
	{
		printf("Key %d present at location %d\n", key, e);
		return e;
	}
	else
	{
		printf("Key Not Present in List\n");
		return -1;
	}
}

Isnt a<=b just shorthand for a<b || a==b?

Isnt a<=b just shorthand for a<b || a==b?