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

Reentrant Locks

Synchronized uses intrinsic locks or monitors. Every object in Java has an intrinsic lock associated with it. Whenever a thread tries to access a synchronized block or method, it acquires the intrinsic lock or the monitor on that object. In the case of static methods, the thread acquires the lock over the class object. ReentrantLock is an explicit locking mechanism.  A reentrant mutual exclusion Lock with the same basic behavior and semantics as the implicit monitor lock accessed using synchronized methods and statements, but with following extended capabilities. Polled and Timed Lock Acquisition Lock.tryLock() is polled lock acquisition mechanism and tryLock(long timeout, TimeUnit unit) is timed lock acquisition mechanism. tryLock() will return immediately. If no other thread locked, then it will return true else returns false. The tryLock(long timeout, TimeUnit unit) will wait for the timeout period to acquire the lock if the lock is not available until timeou...
Post a Comment
Read more

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 ]; } }...
1 comment
Read more

Useful Java Related Resources

Java Tech Videos: http://www.techonvideo.com/category/programming/java/ Java Annotations: http://www.developer.com/java/other/article.php/3556176/An-Introduction-to-Java-Annotations.htm http://download.oracle.com/javase/tutorial/java/javaOO/annotations.html
Post a Comment
Read more