best searching algorithm

Consider a data structure, say, array ‘a’ of size m

  1. Linear Search with complexity O(n)
  2. Binary Search with complexity O(log n)
  3. 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.

One Response to best searching algorithm

  1. Pingback: Find intersection of elements in two arrays | java tech stack

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Mawazo

Mostly technology with occasional sprinkling of other random thoughts

amintabar

Amir Amintabar's personal page

101 Books

Reading my way through Time Magazine's 100 Greatest Novels since 1923 (plus Ulysses)

Seek, Plunnge and more...

My words, my world...

ARRM Foundation

Do not wait for leaders; do it alone, person to person - Mother Teresa

Executive Management

An unexamined life is not worth living – Socrates

Diabolical or Smart

Nitwit, Blubber, Oddment, Tweak !!

javaproffesionals

A topnotch WordPress.com site

thehandwritinganalyst

Just another WordPress.com site

coding algorithms

"An approximate answer to the right problem is worth a good deal more than an exact answer to an approximate problem." -- John Tukey