Archive for Search Algorithms

InterpolationSearch

February 17, 2008 at 8:31 pm · Filed under Search Algorithms ·Tagged

Interpolation search is an improvement on the binary search algorithm. It differs from binary search in that, instead of choosing the position in the middle of the range being searched, we estimate where the target is likely to fall within that range. In the worst case, interpolation search takes linear time. This worst case occurs only if the assumption of uniform distribution is deeply wrong. On average, interpolation search takes time in O(log (log n)), which is extremely small.


public class InterpolationSearch {
public boolean search(double[] data, double target) {
int bottom = 0;
int top = data.length - 1;
while (bottom <= top) {
double lo = data[bottom];
double hi = data[top];
if (lo == hi) {
return target == lo;
}
if ((target hi)) {
return false;
}
double fraction = (target - lo) / (hi - lo);
int midpoint = bottom + (int) ((top - bottom) * fraction);
System.out.println(midpoint);
if (target < data[midpoint]) {
top = midpoint - 1;
} else if (target == data[midpoint]) {
return true;
} else {
bottom = midpoint + 1;
}
}
return false;
}
public static void main(String[] args) {
double[] data=new double[]{4,8,15,16,23,42};
System.out.println(new InterpolationSearch().search(data, 23));
}
}

Leave a Comment

BinarySearch

December 3, 2007 at 5:09 pm · Filed under Search Algorithms ·Tagged

Binary search is a logarithmic algorithm and executes in O(log2n) time.
Specifically, 1 + log2N iterations are needed to return an answer. In most cases it is considerably faster than a linear search. It can be implemented using recursion or iteration, as shown below. In some languages it is more elegantly expressed recursively; however, in some C-based languages tail recursion is not eliminated and the recursive version requires more stack space. http://en.wikipedia.org/wiki/Binary_search_algorithm

package com.search.binary;
import java.util.Arrays;
import com.sort.quick.QuickSort;
public class BinarySearch {
public int search(int[] data, int target) {
int index = -1;
int bottom = 0;
int top = data.length - 1;
while (bottom <= top) {
int middle = (top + bottom) / 2;
if (target < data[middle]) {
top = middle - 1;
} else if (data[middle] == target) {
return middle;
} else {
bottom = middle + 1;
}
}
return index;
}
public static void main(String[] args) {
int[] data = new int[] { 4, 8, 15, 16, 23, 42 };
System.out.println(new BinarySearch().search(data, 16));
}
}

Leave a Comment