Solution: The recursive solution below runs in O(log(n)) because the problem size is halved with each recursive call.

// returns the index of the target element if found, else returns -1 static int Binary_Search(int[] arr, int start, int end, int target) { int medianIndex = (end - start) /2 + start; int medianValue = arr[medianIndex]; if(start == end && arr[start] != target) return -1; if (medianValue == target) return medianIndex; else if (medianValue < target) return Binary_Search(arr, medianIndex + 1, end, target); else return Binary_Search(arr, start, medianIndex - 1, target); }

Thanks for this. Only comment I have is that the line -

ReplyDeleteint medianIndex = (end - start) / 2 + start;

can be simplied to -

int medianIndex = (end + start)/2;

no...(end-start)/2+start is save method to avoid overflow

ReplyDeleteThis answer is WRONG. Try searching the array {2,3} with value 1.

ReplyDeleteFirst iteration: start = 0, end = 1, medianIndex = 0

Second iteration: start = 0, end = -1, medianIndex = 0

Third iteration: start = 0, end = -1, medianIndex = 0

As you can see, it is stuck in an infinite loop!

You need to exclude the situation when start > end to correct the infinite loop mentioned above.

ReplyDelete