Linear and Binary Search PDF

Preview

Summary

Linear and Binary Search...

Description

Sequential and Binary Search Sequential (linear) and binary search are two methods for finding a given element in a list. Sequential search checks every elements of the list, one at a time and in sequence, until the desired element is found or the list ends. Whereas, binary search operates on a sorted list and finds the given element by comparing it with the middle element of the list. The comparison determines whether the middle element is equal to the given element, less than the input or greater. Sequential or Linear Search Sequential search, also known as linear search, is the simplest of all searching algorithms. It is a brute-force approach to locating a given element in a list. It finds the element by starting at the first element of the list and examining each subsequent element until the matching element is found or the list exhausts. Sequential search is proved very useful in the context when you need to search an element in a list quite frequently, and the list may or may not be ordered. In that situation sequential search gets the job done in a brute-force manner. Sequential search might be the most effective search method, depending upon n, the number of elements in the list, and the number of times you will perform such a search. If n is relatively small or you won't be performing the search over the list often, the cost of sorting the elements or using a complex data structure might outweigh the resulting benefits. Sequential search places the fewest restrictions on the type of elements you can search. The only requirement is that there must be a match function to determine whether the target element being searched for matches an element in the list. No additional ordering is required. Java Program for Sequential or Linear Search The implementation of sequential or linear search is trivial. If the list is stored as an array, you need only start at the first element of the array and compare it to the target. If it matches, return true. If not, go to the next element and continue until you find the element you are looking for. If you reach at the end of the list without success, return false. The following program develops a classSequentialSearch containing two overloaded generic methods named sequentialSearch.

/* Java program demonstrating sequential or linear search.*/ import java.util.Iterator; import java.util.*; class SequentialSearch { /* Apply sequential search to search the indexed list (of type T) for the given item. */ public static boolean sequentialSearch (T[] list, T searchKey) { for (T item : list) { if (item.equals(searchKey)) { return true; } } return false; } /* Apply sequential search to iterable collection (of type T) for the given item. */ public static boolean sequentialSearch (Iterable collection, T searchKey) { Iterator iter = collection.iterator( ); while (iter.hasNext()) { if (iter.next( ).equals(searchKey)) { return true; } } return false; } } public class SequentialSearchDemo { public static void main (String[] args)

{ Integer arr[] = {10, 9, 3, 8, 5, 6, 7, 4, 2, 1}; Integer searchKey = new Integer("5"); /* Uses first definition of sequentialSearch and search through the indexed list */ System.out.println("Search key " + searchKey SequentialSearch.sequentialSearch (arr, searchKey));

+ "

is

found?

"

+

ArrayList arrList = new ArrayList(Arrays.asList(arr)); /* Uses second definition of sequentialSearch and search through the iterable collection */ System.out.println("Search

key "

+ searchKey

+ "

is

found?

"

+

SequentialSearch.sequentialSearch (arrList, searchKey)); } } OUTPUT ====== Search key 5 is found? true Search key 5 is found? True Both methods of SequentialSearch are static, therefore it is not needed to create an object of class SequentialSearch in order to call sequentialSearchmethods. Both methods operate on type parameter T that specifies the elements in the collection; T must provide a valid equals(Object o) method. Pros and Cons of Sequential or Linear Search For small lists of unordered elements, sequential search is easy to implement and reasonably efficient. The worst case is when we search for an item not in the list, since we must inspect every element in the list. If the list is large enough and does record frequent additions and deletions then it is better not to apply sequential search on the list. Rather, sort the list once and use binary search. We are discussing binary search in next section.

Binary Search Binary search delivers better performance than sequential search by sorting the elements of the list ahead of searching. Binary search looks at the middle element of the list and see if the element sought-foris found. If not, than it compares the sought-for element with the middle element of the list and check whether the middle element is larger than the element we are trying to find. If so, we keep looking in the first half of the list; otherwise, we look in the second half. It cuts the number of elements to be compared by half. We keep going in the same way until the item is found or it is determined that the sought-for element is not present in the list. The input to binary search is an indexed collection A of elements. Each element A[i]has a key value ki that can be used to identify the element. These keys are totally ordered, which means that given two keys, ki and kj, either kikj. Java Program for Binary Search Given an ordered collection of elements as an array, the following program develops a class BinarySearch that contains a parameterized static method binarySearch for any base type T. Note that Java provides thejava.util. Comparable interface that contains a single method, compareTo. Any class that correctly implements this interface guarantees a total ordering of its instances. import java.util.*; class BinarySearch { /* Apply binary search to search the sorted list (of type T) for the given item. */ public static boolean binarySearch (T[] list, T searchKey) { // null is never included in the list if (searchKey == null) { return false; } int low = 0, high = list.length - 1; while (low 0) { // searchKey is greater than list[i] low = mid + 1; } else { // found the item. return true; } } return false; } } public class BinarySearchDemo { public static void main (String[] args) { Integer arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; Integer searchKey = new Integer("7"); /* Uses binary search and search through the sorted list */ System.out.println("Search key " + searchKey BinarySearch.binarySearch (arr, searchKey)); } }

+ "

is

found?

"

+

OUTPUT ====== Search key 7 is found? True Above binary search implementation in Java uses three important variables: low,high, and mid. low is the lowest index of the current sub-array being searched,high is the upper index of the same sub-array, and mid is the midpoint of the sub-array. Pros and Cons of Binary Search Binary search adds a small amount of complexity for large performance gains. The complexity can increase when the collection is not stored in a simple in-memory data structure, such as an array. There must be a way to access element A[i] for 0...