Commit1bf9cf6

committed

Added the algorithm and test for Exponential Search

1 parent39806e3 commit1bf9cf6Copy full SHA for 1bf9cf6

File tree

+70

-0

lines changed

+70

-0

lines changed

Lines changed: 39 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,39 @@`
	`1`	`+packagesrc.main.java.com.search;`
	`2`	`+`
	`3`	`+importjava.util.Arrays;`
	`4`	`+`
	`5`	`+/**`
	`6`	`+ * Exponential search (also called doubling search or galloping search or Struzik search) is an algorithm which finds`
	`7`	`+ * the position of a target value within an array. It works by determining a range that the search key resides in and`
	`8`	`+ * performing a binary search within that range`
	`9`	`+ * <p>`
	`10`	`+ * Worst-case performanceO(n)`
	`11`	`+ * Best-case performanceO(1)`
	`12`	`+ * Average performanceO(Log n)`
	`13`	`+ * Worst-case space complexityO(Log n)`
	`14`	`+ */`
	`15`	`+publicclassExponentialSearch {`
	`16`	`+/**`
	`17`	`+ * @param array is an array where the element should be found`
	`18`	`+ * @param key is an element which should be found`
	`19`	`+ * @param <T> is any comparable type`
	`20`	`+ * @return The index position of the key in the array, returns -1 for empty array`
	`21`	`+ */`
	`22`	`+public <TextendsComparable<T>>intfindIndex(T[]array,Tkey) {`
	`23`	`+intsize =array.length;`
	`24`	`+if(size ==0)`
	`25`	`+return -1;`
	`26`	`+// If the element is present at first position`
	`27`	`+if (array[0] ==key)`
	`28`	`+return0;`
	`29`	`+`
	`30`	`+// Find the range for binary search by repeated doubling`
	`31`	`+inti =1;`
	`32`	`+while (i <size &&array[i].compareTo(key) <=0) {`
	`33`	`+i =i *2;`
	`34`	`+ }`
	`35`	`+`
	`36`	`+// Call binary search for the range found`
	`37`	`+returnArrays.binarySearch(array,i /2,Math.min(i,size),key);`
	`38`	`+ }`
	`39`	`+}`

Lines changed: 31 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,31 @@`
	`1`	`+packagesrc.test.java.com.search;`
	`2`	`+`
	`3`	`+importorg.junit.Assert;`
	`4`	`+importorg.junit.Test;`
	`5`	`+importsrc.main.java.com.search.ExponentialSearch;`
	`6`	`+`
	`7`	`+publicclassExponentialSearchTest {`
	`8`	`+@Test`
	`9`	`+publicvoidtestExponentialSearch() {`
	`10`	`+ExponentialSearchexpSearch =newExponentialSearch();`
	`11`	`+`
	`12`	`+Integer[]arr = {11,14,23,29,36,40,42,52};`
	`13`	`+intx =36;`
	`14`	`+intindex =expSearch.findIndex(arr,x);`
	`15`	`+Assert.assertEquals("Incorrect index",4,index);`
	`16`	`+`
	`17`	`+Integer[]arrTwo = {-210, -190, -180, -160, -130, -120, -100};`
	`18`	`+x = -120;`
	`19`	`+index =expSearch.findIndex(arrTwo,x);`
	`20`	`+Assert.assertEquals("Incorrect index",5,index);`
	`21`	`+`
	`22`	`+String[]arrString = {"101","122","136","165","225","251","291"};`
	`23`	`+StringstringX ="122";`
	`24`	`+index =expSearch.findIndex(arrString,stringX);`
	`25`	`+Assert.assertEquals("Incorrect index",1,index);`
	`26`	`+`
	`27`	`+String[]arrThree = {};`
	`28`	`+Assert.assertEquals("Incorrect index", -1,expSearch.findIndex(arrThree,""));`
	`29`	`+ }`
	`30`	`+`
	`31`	`+}`

Comments

(0)