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

Find second largest element in an array

Find second largest element in an unsorted array.               We can reach the solution in three ways.  Solution 1 Sort the array and return last but one element. We could use already existing sorting methods in JDK Arrays class and sort the array. public static int findSecondLargestV1( int [] array ){ if ( array . length == 0 || array . length < 2){ return -1; } Arrays.sort( array ); return array [ array . length - 2]; } Complexity: Since this solution depends on sorting, the complexity is equal to complexity of sorting algorithm, ie., O(n log n) Solution 2 public static int findSecondLargestV2( int [] array ){ if ( array . length == 0 || array . length < 2){ return -1; } int max = -1; for ( int i = 0; i < array . length ; i ++){ if ( array [ i ] > max ){ max = array [ i ]; } } int secondMax = -1; for (
1 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