Skip to main content

Binary search (recursive and non-recursive)



Recursive solution:

public static int binarySearch(int[] array, int startIndex, int endIndex, int value){
int midIndex = (startIndex + endIndex)/2;
if(array[midIndex] == value){
return value;
}
if(startIndex > endIndex){
return -1;
}
if(value < array[midIndex]){
int sI = startIndex;
int eI = midIndex - 1;
return binarySearch(array, sI, eI, value);
}else{
int sI = midIndex + 1;
int eI = endIndex;
return binarySearch(array, sI, eI, value);
}
}

 Non-Recursive solution:

public static int binarySearchNoRecursion(int[] array,  int value){
int startIndex = 0;
int endIndex = array.length - 1;
while(startIndex <= endIndex){

int midIndex = (startIndex + endIndex)/2;

if(array[midIndex] == value){
return value;
}

if(value < array[midIndex]){
endIndex = midIndex - 1;
}else{
startIndex = midIndex + 1;
}
}
return -1;

}

Comments

Post a Comment

Popular posts from this blog

Count number of coins needed

Write a method to return the minimum number of coins needed to match a given value. Assume coin denominations are 25, 10, 5, 1. Example: If the value is 101, then we require four 25 cents coins and one 1 cent coin, so total is 5 coins. public static int coinCount( int value ){ int [] denominations = {25, 10, 5, 1}; int coinCount = 0; for ( int i = 0; i < denominations . length ; i ++){ if ( value % denominations [ i ] == 0){ coinCount = coinCount + ( value / denominations [ i ]); break ; } if ( value % denominations [ i ] > 0){ int r = value / denominations [ i ]; coinCount = coinCount + r ; value = value % denominations [ i ]; } } return coinCount ; }
Post a Comment
Read more

Merge two sorted Lists or Arrays

Code to merge two array lists: public static ArrayList<Integer> mergeLists(ArrayList<Integer> l1 , ArrayList<Integer> l2 ){ ArrayList<Integer> l3 = new ArrayList<Integer>(); int i = 0; int j = 0; while ( i < ( l1 .size()) && j < ( l2 .size())){ if ( l1 .get( i ) < l2 .get( j )){ l3 .add( l1 .get( i )); i ++; } else { l3 .add( l2 .get( j )); j ++; } } if ( i < l1 .size()){ while ( i < l1 .size()){ l3 .add( l1 .get( i )); i ++; } } else if ( j < l2 .size()){ while ( j < l2 .size()){ l3 .add( l2 .get( j )); j ++; } } return l3 ; } Code to merge two arrays: public static int[] mergeArrays(int[] a, int[] b){ if((a == null || a.length == 0) && (b == null || b.length == 0)) return new int[0]; if((a == null || a.length == 0)) return b; if(b == n...
Post a Comment
Read more