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