get InOrder sucessor of a given node in a BST

    private Stack<BinarySearchTree> S;
    public int inOrderSuccessor(int data)    {
        S = new Stack<BinarySearchTree>();
        BinarySearchTree Current = getNode(this, data);
        if(Current.right!=null)    {
            return getMin(Current.right).data;
        }    else    {
            BinarySearchTree parent = S.pop();
            if(parent.left==Current)
                return parent.data;
            else
                return S.pop().data;
        }
    }
    private BinarySearchTree getMin(BinarySearchTree T)    {
        while(T.left!=null)
            T=T.left;
        return T;
    }
    private BinarySearchTree getNode(BinarySearchTree T, int data)    {
        if(T==null)    return null;
        else if(data==T.data)        {
            return T;
        }
        else if(data<T.data) {
            S.add(T);
            return getNode(T.left, data);
        }
        else {
            S.add(T);
            return getNode(T.right, data);
        }
    }

Find Index of an element in a Circularly Sorted Array

input=Find 3 in {6,7,8,9,0,1,2,3,4,5};
output=7

    public int FindIndexCircularArray(int element, int[] input)    {
        int high = input.length-1;
        int low = 0;
        while(low<=high)    {
            int mid=(high+low)/2;
            if(element==input[mid])
                return mid;
            else if(input[low]<=input[mid])    {
                //left array is sorted
                if(element>=input[low] && element<input[mid])
                    high=mid-1;
                else    low=mid+1;
            }    else if(input[mid]<=input[high])    {
                //right array is sorted
                if(element>input[mid] && element<=input[high])
                    low=mid+1;
                else    high=mid-1;
            }
        }
        return -1;
    }

Starting Element of a Rotated Array using Binary Search

Sample Input: 
input={6,7,8,9,0,1,2,3,4,5};
output=4
input={0,1,2,3,4,5,6,7,8,9};
output=0

    public int FindStartIndex(int[] input)    {
        int high = input.length-1;
        int low = 0;
        while(low<high)    {
            if(input[low]<=input[high])
                return low;
            int mid=(high+low)/2;
            if(input[mid]<input[mid+1] && input[mid]<input[mid-1])
                return mid;
            else if(input[mid]>input[low])    {
                //left array is sorted
                //start index is not in left
                low=mid+1;
            }    else if(input[mid]<input[high])    {
                //right array is sorted
                //start index is not in right
                high=mid-1;
            }
        }
        return -1;
    }

Count the number of occurrence of an element in an array using Binary Search

    public int FindNumberOfOccurancesInArray(int element, int[] input)    {
        int first=BinarySearchFindIndex(element, input, true);
        if(first==-1)//Doesn't have the element
            return 0;
        else    {
            int second=BinarySearchFindIndex(element, input, false);
            System.out.println(first+" "+second);
            return second-first+1;
        }
    }

This is a module to perform Binary Search
if firstElement = true -> Binary Search returns first occurrence of an element
if firstElement = false -> Binary Search returns last occurrence of an element

    public int BinarySearchFindIndex(int element, int[] input, boolean firstElement)    {
         int high = input.length;
        int low = 0;
        int result =-1;
        while(low<=high)    {
            int mid = low + ((high-low)/2);
            if(element==input[mid])    {
                result = mid;
                if(firstElement)
                    high=mid-1;
                else
                    low=mid+1;
            }    else if(element<input[mid])    {
                high=mid-1;
            }    else if(element>input[mid])    {
                low=mid+1;
            }
        }
        return result;
    }

Simple Binary Search Tree using Java

Input: List of Intigers

public class BinarySearchTree {
    BinarySearchTree left, right;
    int data;

    public BinarySearchTree(int data) {
        System.out.println("newNode "+data);
        this.data = data;
        left=null;
        right=null;
    }

    public void insertElement(int... element)    {
        int size=element.length;
        for(int i=0; i<size; i++)    {
            System.out.println(element[i]);
            insertElement(this, element[i]);
        }
    }

    public void insertElement(int element)    {
        insertElement(this,element);
    }

    private void insertElement(BinarySearchTree T, int element)    {
        if(element==T.data)    {
            System.out.println("ERROR: Data already exist");
        }    else if(T.left == null && T.right ==null)    {
                if(element<T.data)
                    T.left=new BinarySearchTree(element);
                else
                    T.right=new BinarySearchTree(element);
        }    else if(T.left == null)    {
                if(element<T.data)
                    T.left=new BinarySearchTree(element);
                else
                    insertElement(T.right, element);
        }    else if(T.right == null)    {
                if(element>T.data)
                    T.right=new BinarySearchTree(element);
                else
                    insertElement(T.left, element);
        }    else    {    //Root has both Left and Right
                if(element<T.data)
                    insertElement(T.left, element);
                else
                    insertElement(T.right, element);
        }
    }

    public String PreOrder()    {
        return PreOrder(new StringBuffer(), this).toString();
    }
   
    private StringBuffer PreOrder(StringBuffer sb, BinarySearchTree T)    {
        if(T!=null)    {
            PreOrder(sb, T.left);
            PreOrder(sb, T.right);
            sb.append(T.data).append(", ");
            return sb;
        }    else return sb;
    }
   
    public String PostOrder()    {
        return PostOrder(new StringBuffer(), this).toString();
    }
   
    private StringBuffer PostOrder(StringBuffer sb, BinarySearchTree T)    {
        if(T!=null)    {
            sb.append(T.data).append(", ");
            PreOrder(sb, T.left);
            PreOrder(sb, T.right);
            return sb;
        }    else return sb;
    }
   
    public String InOrder()    {
        return InOrder(new StringBuffer(), this).toString();
    }
   
    private StringBuffer InOrder(StringBuffer sb, BinarySearchTree T)    {
        if(T!=null)    {
            InOrder(sb, T.left);
            sb.append(T.data).append(", ");
            InOrder(sb, T.right);
            return sb;
        }    else return sb;
    }
}

Linked List Binary Search

 This  is a program to perform Binary Search in a Sorted Linked List

Input: Sorted List of Elements:

    public int Search(int element)    {
        return Search(element, 1, sizeOfList());
    }
   
    private int Search(int element, int StartinDex, int EndInDex) {
        LinkedList L = this;
        int middle = (StartinDex+EndInDex)/2;
        if(L.getValue(middle)==element)    {
            return middle;
        }    else if(L.getValue(middle)<element)    {
            return Search(element, middle+1, EndInDex);
        }    else    {
            return Search(element, StartinDex, middle-1);
        }
    }

 For Linked List Code, look at this link

Binary Search in an Array

Input is an sorted array and an element which need to be searched in the array. The module will return the possition of the element in the given array.

public class BinarySearchArray {
    private final static int Default = -999; //default value
   
    public int BinarySearch(ArrayList<Integer> input, int element)    {
        if(input.size() == 0)
            return Default;
        return BinarySearchRecursive(input, element, 0, input.size());
    }
   
    private int BinarySearchRecursive(ArrayList<Integer> input, int element, int min, int max)    {
        int possition = Default;
        int check_possition = min+((max-min)/2);
        if(input.get(check_possition) == element)
            possition = check_possition;
        else if(max <= min)
            return Default;    //element not found
        else if(element > input.get(check_possition))    {
            int difference = (max-min)/2;
            if(difference == 0) difference = 1;
            min = min + (difference);
            possition = BinarySearchRecursive(input, element, min, max);
        }    else    {
            max = check_possition-1;
            possition = BinarySearchRecursive(input, element, min, max);
        }
        return possition;
    }
}
-----------------------------------------------------------------------------------------------------------
Recursion costs more memory. To be more memory efficient we can use a loop instead of recursion.

public class BinarySearchInLoop {
    private final static int Default = -999; //default value
    public int BinarySearch(ArrayList<Integer> input, int element)    {
        if(input.size() == 0)
            return Default;
        else {
        int min = 0;
        int max = input.size();
        while(min <= max) {
            int check_possition = min+((max-min)/2);
            if(input.get(check_possition) == element) {
            return check_possition;
            } else if(element > input.get(check_possition))    {
            int difference = (max-min)/2;
                    if(difference == 0) difference = 1;
                    min = min + (difference);
            } else {
            max = check_possition-1;
            }
            }
        return Default;
        }
    }
}