1. Searching in collections
The following article will discuss the implementation of
different search algorithms in Java for finding elements in a
collections.
Searching in collection is done to answer the questions:
-
Does the element exists in the collections
-
Get the element from the collection
-
Delete the element from the collection
Collection in this article is used in the broader sense and not
in the strict Java sense. For example collection we are looking at my
be array or lists.
Sequential search is the simplest approach. Given a collection
you try every element in the collection until you have found the
element or until you reach the end of the collection.
Sequential Search is extremely easy to implement.
Create the Java project
"de.vogella.algorithms.search.sequential" and a package with the same
name.
Create the following program.
package de.vogella.algorithms.search.sequential;
public class SequentialSearch {
public static boolean contains(int[] a, int b){
for (int i : a) {
if (i==b){
return true;
}
}
return false;
}
}
You can use the following JUnit test to validate your sort
method. To
learn about JUnit please see
JUnit Tutorial.
package de.vogella.algorithms.search.sequential;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import org.junit.Test;
public class SequentialSearchTest {
@Test
public void testContains() {
int[]a = {1, 2, 3, 4, 5, 19, 17, 7};
assertTrue(SequentialSearch.contains(a, 17));
assertTrue(SequentialSearch.contains(a, 1));
assertTrue(SequentialSearch.contains(a, 2));
assertTrue(SequentialSearch.contains(a, 3));
assertTrue(SequentialSearch.contains(a, 4));
assertFalse(SequentialSearch.contains(a, 10));
}
}
See
Complexity Analysis
for an introduction to the topic.
Sequential search has a average and worst-case runtime of O(N).
Binary search requires that the collection is already sorted. For
example by
Quicksort
or
http://www.vogella.com/tutorials/JavaAlgorithmsMergesort/article.html
Mergesort. Binary search checks the element in the middle of the
collection.
If the search element smaller or greater then the found
element then a sub-array is defined which is then search again.
If the
searched element is smaller then the found element then the sub-array
is from the start of the array until the found element. If the
searched element is larger then the found element then the sub-array
is from the found element until the end of the array. Once the
searched
element is found or the collection is empty then the search
is over.
Create the Java project
"de.vogella.algorithms.search.binary" and
a package with the same
name.
Create the following program.
package de.vogella.algorithms.search.binary;
public class BinarySearch {
public static boolean contains(int[] a, int b) {
if (a.length == 0) {
return false;
}
int low = 0;
int high = a.length-1;
while(low <= high) {
int middle = (low+high) /2;
if (b> a[middle]){
low = middle +1;
} else if (b< a[middle]){
high = middle -1;
} else {
return true;
}
}
return false;
}
}
You can use the following JUnit test to validate your sort
method. To
learn about JUnit please see
JUnit Tutorial.
package de.vogella.algorithms.search.binary;
import org.junit.Test;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
public class BinarySearchTest {
@Test
public void testContains() {
int[]a = {1, 2, 3, 4, 5, 7, 17, 19 };
assertTrue(BinarySearch.contains(a, 1));
assertTrue(BinarySearch.contains(a, 2));
assertTrue(BinarySearch.contains(a, 3));
assertTrue(BinarySearch.contains(a, 4));
assertFalse(BinarySearch.contains(a, 10));
}
}
See
Complexity Analysis
for an introduction to the topic.
Binary search cuts the search space in each iteration into half
and has therefore O(lg N) runtime behavior.
This tutorial is Open Content under the
CC BY-NC-SA 3.0 DE
license. Source code in this tutorial is distributed under the
Eclipse Public License.
See the
vogella License page
for details on the terms of reuse.
Writing and updating these tutorials is a lot of work.
If this free community service was helpful,
you can support the cause by giving a tip
as well as reporting typos and factual errors.
Best technological website!! Algorithm explained in detail. Thanks for sharing.
ReplyDeleteCheers,
http://www.flowerbrackets.com/how-to-implement-quick-sort-in-java-program/
Nice explanation with examples and appropriate links. Thanks for sharing.
ReplyDeleteCheers,
http://www.flowerbrackets.com/java-merge-sort/