Sunday, 23 August 2015

Recursive implementation of Binary search

Write a recursive function that searches for a target in a sorted array using binary search.
import java.util.Objects;

public class BinarySearch {
 private int arr[];

 public BinarySearch(int arr[]) {
  this.arr = arr;
 }

 /* Return index of element if exist, else -1 */
 public int search(int ele) {
  Objects.nonNull(arr);
  if (arr.length == 0)
   return -1;
  return search(ele, 0, arr.length - 1);
 }

 private int search(int ele, int start, int end) {
  int mid = (start + end) / 2;

  if (start > end)
   return -1;

  if (arr[mid] == ele)
   return mid;
  else if (arr[mid] > ele)
   return search(ele, start, mid - 1);
  else
   return search(ele, mid + 1, end);
 }
}


Following is the junit test case.
import static org.junit.Assert.*;

import org.junit.Test;

public class BinarySearchTest {

 @Test
 public void test1(){
  int arr[] = {1,2,3,4,5,6};
  BinarySearch search = new BinarySearch(arr);
  
  assertEquals(search.search(1), 0);
  assertEquals(search.search(2), 1);
  assertEquals(search.search(3), 2);
  assertEquals(search.search(4), 3);
  assertEquals(search.search(5), 4);
  assertEquals(search.search(6), 5);
  assertEquals(search.search(0), -1);
  assertEquals(search.search(15), -1);
  
  int arr1[] = new int[0];
  search = new BinarySearch(arr1);
  assertEquals(search.search(1), -1);
  
  int arr2[] = {2, 4};
  search = new BinarySearch(arr2);
  assertEquals(search.search(1), -1);
  assertEquals(search.search(5), -1);
  assertEquals(search.search(4), 1);
 }
}


No comments:

Post a Comment