1. If the array is arranged in ascending or descending order, several searching techniques are available that can be that can be used to improve search efficiency.
2. Of all there techniques, Binary search is most commonly used. Binary search starts by initializing low to 0 and high to n-1 where n is the number of elements in the original array
3. In each parce of binary search the key is searched at position mid where mid is evaluated as mid= (low+high)/2.That is the key is always compared with the middle element.
4. If the required key is present at position mid, then search stops. Otherwise low changes to mid+1 if key is greater than middle element or high changes to mid-1 if key is lesser than the middle element.
5. Every pass of binary search reduces the number of candidates by the factor of 2, hence the name binary.

6. Program to demonstrate binary search //Assume that the array is sorted in ascending order

   Import.java.io.*;
   Class BinarySearch
   {
   public static void main(String args[]) throws IOException
   {
       InputStreamReader isr = new InputStreamReader(System.in);
       BufferedReader stdin = new BufferedReader(isr);
       int i, n ,key;
       System.out.println(“Enter the number of elements:”);
       n=Integer.parseInt(stdin.readLine());
       int x[] = new int[n];
   
       System.out.println(“Enter the elements:”);
       for (i=0;i<n;i++)
           x [i] = Integer.parseInt(stdin.readLine());
       System.out.println(“Enter the elements to be searched:”);
       key = Integer.parseInt(stdin.readLine());
       i=binary(x, key, 0, n-1);
       if(i==1)
           System.out.println(key+“not found”);
       else
           System.out.println( key+“ found at position “+i);
   }
   public static int binary(int x[], int key, int low, int high)
   {
       Int mid;
       if(low>high)
           return(-1);
       mid=(low+high)/2;
       if(key==x[mid])
           return(mid)
       else
       if(key<x[mid])
           return(binary(x,key,low,mid-1));
       else
           return(binary(x,key,mid+1,high));
   }
   }
   

Deriving Complexity of binary search:

• Consider I, such that 2i>= (N+1)
• Thus, 2i-1-1 is the maximum number of comparisons that are left with first comparison.
• Similarly 2i-2-1 is maximum number of comparisons left with second comparison.
• In general we say that 2i-k-1 is the maximum number of comparisons that are left after ‘k’ comparisons. If the number of elements are left then the desired data item is obtained by ith comparisons.

• Thus, the maximum number of comparisons required for successful search is:

  $Cms= i \\ or \ \ Cms= log2 (N +1)$

• For unsuccessful search, the maximum number of comparisons:

  Cms = Cmv

  for, computing average number of comparisons ‘Cs’ indicates successful search.

  $Cs = C/N \\ C = i*2i - (20 + 21 + 22 +……..2(i-1)) \\ = i + 2i (i-1)$

• Now, consider that the probability for searching a requested data item is 1/n, then,

  $Cs = (1 + 2i (1- i)/n) \\ Cs = [1+ (N +1)(log 2 (N +1)-1)]/n \\ Cs = log2 N (for \ large N)$

• It can be easily observed that for successful and unsuccessful search the expected number of cases is given by:

  $Cs = C4 = O (log2 N)$

• It should be noted that Binary Search provides to be more efficient than the sequential search. But when implemented with linked lists it would not be efficient.

• On the basis of the above analysis the time complexity of Binary Search is:

  E(n) = [log2 n] +1, it is actually 2E(a) >n, that is O(log2 n).