Twopair sum[Fast], Prime Sieve, Binary Search

Methods.java

public class Methods{

  /*O(N)- Two pair search in a sorted array
    It is much better than heap cration, tree creation. 
    Does work in place and O(1) extra space
  */
  
  public int twoPairSum(int[] a. int k){
    
      int i=0, j= a.length-1;
      while(i<a.length){
          while(j>0 && a[j]+a[i]>k) j--;
          if(a[j]+a[i]==k) ++count;
          i++;
          j= a.length-1;
      }
    
  
  }
  
  /*
  PRIME SIEVE - implementation main part 
  isPrime - is a boolean array saying whether ith integer is a prime or not (1-N)
  */
  boolean[] isPrime = new boolean[N+1];
  
  for(int factor=2; factor*factor<=isPrime.length; factor++){            
      if(isPrime[factor]){
          for(int j=2;factor*j<=isPrime.length; j++){
              isPrime[factor*j]=false;
          }
      }
  }
  
  /*
  BINARY SEARCH - implementation 
  [non recursive] - returns index of the value or -1 if it is not present
  */
  
  int binarySearch(int[] A, int key){
      int lo=0,hi=A.length-1;
      while(lo<=hi){
          int mid = lo+ (hi-lo)/2;
          int cmp = A[mid]-key;
          if(cmp>0) hi = mid-1;
          else if(cmp<0) lo = mid+1;
          else return mid;
      }  
      return -1;
  }
  
  /*
  BINARY SEARCH - implementation 
  [recursive] - returns index of the value or -1 if it is not present
  */
  
  int binarySearch(int[] A, int key, int beg, int end){
      int lo=beg,hi=end;
      while(lo<=hi){
          int mid = lo+ (hi-lo)/2;
          int cmp = A[mid]-key;
          if(cmp>0) return binarySearch(A,key,lo,mid-1);
          else if(cmp<0) return binarySearch(A,key,mid+1,hi);
          else return mid;
      }  
      return -1;
  }
  
  
  
}