Binary Search: Searching Algorithm

The prerequisite for Binary search is that the input array elements must be in Sorted order.

Binary search maintains a contiguous subsequence of the sorting sequence where the target value is surely located. This is called "Search space".
The search space is initially the entire sequence.

At each step, the algorithm compares the median value in the search space to the target value.
Based on the comparison, and because the sequence is sorted, it can then eliminate half of the search space. By doing this repeatedly, it will eventually be left with a search space consisting of a single element, the target value.

Java code:

import java.util.Arrays;

class BinarySearch {
        static public int binarySearch(int[] in, int low, int high, int key) {
                if(low > high)
                        return -1;

                int mid = (low + high)/2;

                if(in[mid] == key)
                        return mid;
                else if(key < in[mid])
                        return binarySearch(in, low, mid-1, key);
                else
                        return binarySearch(in, mid+1, high, key);
        }

        static public int nonRecBinarySearch(int[] in, int key) {
                int low = 0, high = in.length-1;
                int mid = -1;

                while(low <= high) {
                        mid = (low + high)/2;

                        if(in[mid] == key)
                                break;
                        else if(key < in[mid])
                                high = mid - 1;
                        else
                                low = mid + 1;
                }

                return mid;
        }

        static public void main(String[] args) {
                int[] in = {1, 2, 3, 5, 9, 12, 19, 25, 32};

                int pos = nonRecBinarySearch(in, 25);

                System.out.println(Arrays.toString(in));
                System.out.println("Position of: " + 25 + " is: " + pos);
        }
}

Notes:
If the array is not sorted, then Linear search is better compared to binary search.
In Binary search, after each iteration, the length of the array gets cut into half.

Efficiency:

Worst Case:
To get the worst case complexity of Binary search, we need to check the number of iterations that are performed before "low>high"
After 1 st iteration : n/2 items remaining
After 2nd iteration : n/4 items remaining
.
.
.
After kth iteration : n/2^k items remaining

The last iteration occurs when n/2^k >= 1 and n/2^(k+1) < 1 items remaining
n/2^k >=1
=> n >= 2^k
=> log(n) >= log(2^k)
k<=log(n)
Worst case running time = O(log n)

Best Case:
Best case in binary search happens when the search element is in the middle of the array, so that it can be found in the first attempt itself.

Number of comparisons = 1

Therefor, Worst case time Complexity = O(1)

Average Case:
//TODO: