In this article lets look in to the implementation of basic searching algorithms in java.
One of the important operation that a programmer encounters every day is Searching. It involves searching a given number against a collection, a particular name from a set of employee names and also searching records in a DB. Whatever may be the scenario involved with searching, in comes under three basic algorithm.
1. Linear Search
2. Binary Search
3. Hash Search
As the name suggest, Linear search involves searching for the given element from a list by comparing the search element with every element in the list sequentially.
It is a simple and straight forward algorithm with time complexity of 0(n).
Binary search involves dividing a sorted list to be searched and narrowing down the search range till the search element is found. It is similar to searching a word in dictionary. The time complexity is 0(log n). It is a sophisticated algorithm, as it involves for eg. just 20 comparisons for 10 million items.
The disadvantage is that the list which is to be searched has to be sorted. Ok! But there is better algorithm than binary search, which will reduce the search time complexity to at least 1, (i.e) the best case results in directly locating the search value from the list. It is called hash search. Initially an hash table is to be formed using the given list of items. Then the array elements will be stored in index positions based on their hash value.
The hash value is calculated using a hashing technique. Here we have made it simple by using the formula (position = elementValue%arraySize). The array size has to be chosen carefully so that there are not much empty or null values in array. In java empty or null values in integer arrays are not possible, so we use Integer.MIN_VALUE(-2147483648) for representing empty values in array. If more than one element falls in the same position it will be stored in the next available location. So hash search mostly results in the locating the search key in one or two comparisons and worst case being n-1.
The below program contains binary search and hash search algorithm. Since linear search is a straight forward algorithm, we have left it as a homework for the readers!
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS''
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS
* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/
package in.techdive.java.examples;
/**
* This class contains implementation methods for basic Searching algorithms
*/
public class SearchingAlgorithm
{
public SearchingAlgorithm()
{
}
public static void main(String[] args)
{
SearchingAlgorithm searchAlgorithm = new SearchingAlgorithm();
int srchElement = 611;
int a[] = new int[] { 1, 2, 6, 19, 21, 34, 53 };
/* Binary Search */
System.out.println("Binary Search ");
System.out.println("Input Array :");
searchAlgorithm.printArr(a);
System.out.println();
System.out.println("Search Element is ->" + srchElement);
searchAlgorithm.binarySeach(a, srchElement);
/* Hash Search */
System.out.println("Hash Search ");
System.out.println("Input Array :");
a = new int[] { 611, 2, 3, 4, 6, 53, 21, 34, 19 };
searchAlgorithm.printArr(a);
System.out.println();
System.out.println("Generate Hash Table :");
int[] b = searchAlgorithm.generateHashTable(a);
System.out.println("Search Element is ->" + srchElement);
searchAlgorithm.hashSearch(b, srchElement);
}
/**
* This method searches for the element passed as the parameter in the given array using Binary Search Algorithm.
*
* The time complexity of binary search is o(log n).
*/
public void binarySeach(int[] finalArr, int searchElem)
{
int lowerLimit = 0;
int upperLimit = finalArr.length;
while ((lowerLimit + 1) != upperLimit)
{
int middle = (lowerLimit + upperLimit) / 2;
if (searchElem > finalArr[middle])
{
lowerLimit = middle;
}
else if (searchElem == finalArr[middle])
{
System.out.println("element " + searchElem
+ " found at position -> " + middle);
return;
}
else
{
upperLimit = middle;
}
}
if (lowerLimit == searchElem)
{
System.out.println("element " + searchElem
+ " found at positon -> " + lowerLimit);
}
else if (upperLimit == searchElem)
{
System.out.println("element " + searchElem
+ " found at position -> " + upperLimit);
}
else
{
System.out.println("element " + searchElem + " not found");
}
}
/**
* This method takes an array as argument and returns another array with size >= the given array with
* same set of elements. The index positions of array elements will be changed based on hashing logic.
* If the resulting array size is greater then excess index positions will be occupied by (Integer.MIN_VALUE)
* Once the array element positions are changed , it will be easy to locate an element based on the hashing
* logic at the best case of 1 and worst case of n-1.
*/
public int[] generateHashTable(int[] a)
{
int tabSize = a.length;
int max = a[0];
for (int k = 0; k < a.length; k++)
{
if (a[k] > max)
{
max = a[k];
}
}
tabSize = a.length;
boolean sel = false;
while (sel == false)
{
if (max % tabSize > tabSize)
{
tabSize = tabSize + 1;
}
else
{
sel = true;
}
}
int[] b = new int[tabSize];
for (int i = 0; i < tabSize; i++)
{
b[i] = Integer.MIN_VALUE;
}
for (int i = 0; i < a.length; i++)
{
int pos = a[i] % tabSize;
pos--;
if (b[pos] == Integer.MIN_VALUE)
{
b[pos] = a[i];
}
else
{
for (int m = pos + 1; m < a.length; m++)
{
if (b[m] == Integer.MIN_VALUE)
{
b[m] = a[i];
break;
}
if (m + 1 == a.length)
{
m = 0;
}
if (m == pos)
{
break;
}
}
}
}
printArr(b);
return b;
}
/**
* This method searches for the element passed as the parameter in the given array(or hash table) using
* Hash Search Algorithm The time complexity of hash search is 1 for best case and n-1 for best case.
*/
public void hashSearch(int[] a, int srchKey)
{
int pos = srchKey % a.length;
pos--;
if (a[pos] == srchKey)
{
System.out.println("Search element found at position -> " + pos);
return;
}
else
{
for (int m = pos + 1; m < a.length; m++)
{
if (a[m] == srchKey)
{
System.out.println("Search element found at position -> " + pos);
return;
}
if (m + 1 == a.length)
{
m = 0;
}
if (m == pos)
{
break;
}
}
System.out.println("Element not found");
}
}
public void printArr(int[] a)
{
for (int i = 0; i < a.length; i++)
{
System.out.print(a[i] + " ");
}
}
}
Output:
Binary Search
Input Array :
1 2 6 19 21 34 53
Search Element is ->611
element 611 not found
Hash Search
Input Array :
611 2 3 4 6 53 21 34 19
Generate Hash Table :
19 2 3 4 21 6 34 611 53 Search Element is ->611
Search element found at position -> 7