CareerCup

Can you please explain the problem little bit. Thanks.

Yse Ternary Operator

bool BinSearch(int arr[], int elem, int left, int right)
{
int mid = (left+right)/2;

if (arr[mid]== elem)
{
printf("Element found at [%d] Position", mid);
} else {
(arr[mid]>elem)?BinSearch(arr, elem, left, mid):BinSearch(BinSearch(arr, elem, mid+1, right));
}

printf("Element Not Found");

}

I don't know why people try to ask micro-code optimization questions in interviews.

Anyway, here is one approach

// Calculates 'positiveness' of given integer
// Returns 1 is x > 0, and 0 if x < 0.
// Assume 32 bit integer and left most bit is sign bit.
// x = 0 is invalid input.

int Positivity(int x) {
    return -(x & (0x80000000));
}

bool BinarySearch(int [] arr, int key, int left, int right) {
    
    int mid = (left+right)/2;
    
    if (arr[mid] == key) {
        return true;
    }
    
    int posit = Positivity(key - arr[mid]);

    int newLeft = mid*posit + (1-posit)*left;
    int newRight = right*posit + (1-posit)*mid;
    
    return BinarySearch(arr, key, newLeft, newRight);

}

// There might be bugs, but you get the idea.

You should be able to fix it yourself, if you actually have the written the code and can debug it.

The idea is to get the sign bit and use that. The current code assume 32 bit integers and yes, it is not portable.

Perhaps you can fix the code and post it here...

The original question is a bit silly, anyway.

The goal as I understand is to avoid 2 comparisons and maker only one.
Lets say n is 'your' number and k is the key.
Normally, we'd check: n < k => go left; n > k => go right.

Instead, just check mod(n-k) > 0 => go right; else go left.

low = 0
high = N
while (low < high) {
mid = low + ((high - low) / 2) // Note: not (low + high) / 2 !!
if (A[mid] < value)
low = mid + 1;
else
//can't be high = mid-1: here A[mid] >= value,
//so high can't be < mid if A[mid] == value
high = mid;
}
// high == low, using high or low depends on taste
if ((low < N) && (A[low] == value))
return low // found
else
return -1 // not found

int BinSrch(int *array,int n){    
                int low=0,high=n-1;
  		while (low < high) {
                  mid = (low + high) / 2;
                  if (key > array[mid])
                        low = mid + 1;
                  else
                        high = mid; 
                }
                /* here low == high */
	        if (low < n && array[low] == key)
		  return 1;         /* search_key found at low */
	        else return 0;
             }

This can be done by comparing only a single time as described below :-
Pseudo code :-

int bSearch(int nArray[], int nLength, int nVal)
//

int nRes <- -1
int nStart <- 0
int nEnd <- nLength - 1
while nStart <= nEnd
do
- int nMid <- (nStart + nEnd) / 2
- if nVal > nArray[nMid]
- then
- - nEnd <- nMid - 1
- else
- - nRes <- nMid
- - nStart <- nMid + 1

return nRes

function _binarySearch2(arr, start, end, val) {
	if (start === end)
		if (arr[start] === val)
			return start;
		else
			return -1;

	const mid = parseInt((start + end) / 2);

	if (val > arr[mid])
		return _binarySearch2(arr, mid + 1, end, val);
	else
		return _binarySearch2(arr, start, mid, val);
}

function binarySearch2(arr, val) {
	if (!arr.length)
		return -1;

	return _binarySearch2(arr, 0, arr.length - 1, val);
}

const arr = [4, 5, 7, 8];

console.log(binarySearch2(arr, 7));

function _binarySearch2(arr, start, end, val) {
	if (start === end)
		if (arr[start] === val)
			return start;
		else
			return -1;

	const mid = parseInt((start + end) / 2);

	if (val > arr[mid])
		return _binarySearch2(arr, mid + 1, end, val);
	else
		return _binarySearch2(arr, start, mid, val);
}

function binarySearch2(arr, val) {
	if (!arr.length)
		return -1;

	return _binarySearch2(arr, 0, arr.length - 1, val);
}

const arr = [4, 5, 7, 8];

console.log(binarySearch2(arr, 7));