Function to perform Binary Search on a Sorted Array

Problem: Write a function to perform a binary search on a Sorted Array.

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);
        }

4 comments:

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

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

    can be simplied to -

    int medianIndex = (end + start)/2;

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

    ReplyDelete
  3. This answer is WRONG. Try searching the array {2,3} with value 1.
    First 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!

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

    ReplyDelete