///// Arithmetic Dichotomy// 20060310 by daineng@nj.cpsecure///
#include <iostream>#include <string>
int iArray[] = {22, 33, 44, 55, 66, 77, 88};
string sArray[] = { string("AElig"), string("Aacute"), string("Acirc"), string("zeta")};
template<class T>int look_up(T val, T array[], int arr_size){ int low, high, mid, cmp; low = 0; high = arr_size - 1; while (low <= high) { mid = (low + high) / 2; //cout << "low=" << low << "; mid=" << mid << "; high=" << high << endl; if (val > array[mid]) low = mid + 1; else if (val < array[mid]) high = mid - 1; else return mid; } return -1;}
template<class T>void print_result(int index, T array[]) { if (index >= 0) cout << "Found @ " << index << " : " << array[index] << endl; else cout << "Not Found!" << endl;}
int main(void){ int index; index = look_up(88, iArray, sizeof(iArray)/sizeof(int)); print_result(index, iArray); index = look_up(0, iArray, sizeof(iArray)/sizeof(int)); print_result(index, iArray); //cout << "Size of Array : " << sizeof(sArray)/sizeof(string) << endl; index = look_up(string("Acirc"), sArray, sizeof(sArray)/sizeof(string)); print_result(index, sArray);}
#!/usr/bin/python# Filename: dichotomy.py# 20060310 by daineng@nj.cpsecure
iList = [11, 22, 33, 44, 55, 66, 77]sList = ['apple', 'orange', 'banana', 'mango']
def look_up(val, list, size): '''Dichotomy Search''' low = 0 high = size - 1 while low <= high: mid = (low + high) / 2 #print 'low=%d; mid=%d, high=%d' % (low, mid, high) if val > list[mid]: low = mid + 1 elif val < list[mid]: high = mid - 1 else: print 'Found @ %d : %s' % (mid, list[mid]) return mid print '"%s" Not Found.' % (val) return -1
print iListindex = look_up(11, iList, len(iList))index = look_up(55, iList, len(iList))index = look_up(88, iList, len(iList))
print sListsList.sort()print sList
index = look_up('mango', sList, len(sList))index = look_up('cccc', sList, len(sList))
