October 5, 2012
by Niranjan Tallapalli
Consider a data structure, say, array ‘a’ of size m
- Linear Search with complexity O(n)
- Binary Search with complexity O(log n)
- Search using HASH value with complexity O(1)
Linear Search with complexity O(n):
Here for a given element, say a[i], we have to traverse the entire data structure till we find the element, so in the worst case we have to traverse till end of the DS and hence the order/complexity of linear search is O(n)
This is a brute force way of doing it.
pros:
suitable for smaller sized data structures
suitable for data structures which are not sorted
simpler approach, simple and less code (KISS principle)
cons:
for large sized data structures this wont do any good in terms of time complexity
Binary Search with complexity O(log n):
Binary search implements divide and conquer algorithm to search for a required element in the data structure. But to do a binary search on the data structure(DS), DS elements needed to be in sorted manner. (see best sorting algorithms)
Every iteration we divide the array by 2 and then see which side the element (to be searched) falls (lower half or upper half) and recursively do the same thing till the element is found.
logarithm is just a mathematical scale to represent number system in powers of base, in binary search case, base=2 (because every time we divide the DS by two in one way also implies raising the power by 2 in other way)
Example:
1,3,5,7,10,12,16,19
Here we have 8 elements, so every time we divide by half, we can pin point to any element within three iterations, that is, lets assume we are searching for ’19’
First Iteration:
step 1: pivot = a[(0+7)/2) = a[3] = 7
step 2: Since 19>7, ignore left side of pivot and consider right side array of pivot, that is, 10,12,16,19
Second Iteration:
step 1: pivot = a[(0+3)/2) = a[1] = 12
step 2: Since 19>12, ignore left side of pivot and consider right side array of pivot, that is, 16,19
Third Iteration:
step 1: pivot = a[(0+1)/2) = a[0] = 16
step 2: Since 19>16, ignore left side of pivot and consider right side array of pivot, that is, 19, return this value
hence number of elements =8=2^3=3(in log with base 2 scale), therefore the complexity of binary search algorithm is O(log n)
/**
* @author ntallapa
*
*/
public class BinarySearch {
/**
*
* @param a integer array to be searched
* @param value element of the array to be searched
* @param left left most index of the passed array
* @param right most index of the passed array
* @return element value if found else -1 if not found
*/
public int binarySearch(int[] a, int value, int left, int right) {
// choose pivot index element as middle element
int idx = (left+right)/2;
// check if pivot index exists in the array
if(idx>=a.length) {
return -1;
}
int pivot = a[idx];
if(left > right)
return -1;
if(value < pivot) {
right = idx-1;
return binarySearch(a, value, left, right);
} else if(value > pivot) {
left = idx+1;
return binarySearch(a, value, left, right);
} else {
return pivot;
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = {1,2,3,4,5};
BinarySearch bs = new BinarySearch();
System.out.println(bs.binarySearch(a, 3, 0, a.length));
}
}
pros:
Best suitable for large sized arrays
cons:
array elements must be sorted prior to search
Search using HASH value with complexity O(1):
Insert the elements of the data structure into a hash implemented data structure like Hashtable or HashMap and you are good to go with one line statement:
hashArr.contains(a[i])
Since the elements of hashmap are indexed by hashcode, the time to search for any particular element would almost be = 1 (CONSTANT time)
pros:
Best in case of medium-large sized arrays
cons:
If the array is very large then it might lead to collisions in the hash implemented DS
Additional space requirements to store array elements into hashmap
WHICH ONE TO USE:
It is actually a trade off between these three approaches on which one to use. There is never always one best approach to follow blindly. We should analyze the scenario and adopt one of these.
coding algorithms 
Recent Comments