// orderedArray.java
// demonstrates ordered array class
// to run this program: C>java OrderedApp
////////////////////////////////////////////////////////////////
class OrdArray 
{
private long[] a; // ref to array a
private int nElems; // number of data items
// -----------------------------------------------------------
public OrdArray(int max) // constructor
{
a = new long[max]; // create array
nElems = 0;
}
// -----------------------------------------------------------
public int size() {
return nElems;
}
// -----------------------------------------------------------
public int find(long searchKey) {
int lowerBound = 0;
int upperBound = nElems - 1;
int curIn;
while (true) {
curIn = (lowerBound + upperBound) / 2;
if (a[curIn] == searchKey)
return curIn; // found it
else if (lowerBound > upperBound)
return nElems; // can't find it
else // divide range
{
if (a[curIn] < searchKey)
lowerBound = curIn + 1; // it's in upper half
else
upperBound = curIn - 1; // it's in lower half
} // end else divide range
} // end while
} // end find()
// -----------------------------------------------------------
public void insert(long value) // put element into array
{
int j;
for (j = 0; j < nElems; j++)
// find where it goes
if (a[j] > value) // (linear search)
break;
for (int k = nElems; k > j; k--)
// move bigger ones up
a[k] = a[k - 1];
a[j] = value; // insert it
nElems++; // increment size
} // end insert()
// -----------------------------------------------------------
public boolean delete(long value) {
int j = find(value);
if (j == nElems) // can't find it
return false;
else // found it
{
for (int k = j; k < nElems; k++)
// move bigger ones down
a[k] = a[k + 1];
nElems--; // decrement size
return true;
}
} // end delete()
// -----------------------------------------------------------
public void display() // displays array contents
{
for (int j = 0; j < nElems; j++)
// for each element,
System.out.print(a[j] + " "); // display it
System.out.println("");
}
// -----------------------------------------------------------
} // end class OrdArray
// //////////////////////////////////////////////////////////////
class OrderedApp {
public static void main(String[] args) {
int maxSize = 100; // array size
OrdArray arr; // reference to array
arr = new OrdArray(maxSize); // create the array
arr.insert(77); // insert 10 items
arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.insert(88);
arr.insert(11);
arr.insert(00);
arr.insert(66);
arr.insert(33);
int searchKey = 55; // search for item
if (arr.find(searchKey) != arr.size())
System.out.println("Found " + searchKey);
else
System.out.println("Can't find " + searchKey);
arr.display(); // display items
arr.delete(00); // delete 3 items
arr.delete(55);
arr.delete(99);
arr.display(); // display items again
} // end main()
} // end class OrderedApp
二分查找的递归算法程序：
public class Search {
public static int find(int[] data, int goal, int left, int right) {
int mid = (left + right) / 2;
if (left > right) {
return -1;
}
if (goal == data[mid]) {
return mid;
} else if (goal < data[mid]) {
return find(data, goal, left, mid - 1);
} else if (goal > data[mid]) {
return find(data, goal, mid + 1, right);
}
return -1;
}
public static void main(String[] args) {
int[] data = new int[] { 1, 2, 4, 6, 7 };
int result = find(data, 6, 0, data.length - 1);
System.out.println(result);
}
}
二分查找的迭代算法程序：
public class BinarySearch {
public static void main(String[] args) {
int[] a = { 1, 3, 4, 5, 7, 9, 11, 15 };
System.out.println(binarySearch(a, 9));
}
public static int binarySearch(int[] a, int key) {
int first = 0;
int last = a.length - 1;
int mid;
while (first <= last) {
mid = (first + last) / 2;
if (a[mid] == key)
return mid;
if (a[mid] > key)
last = mid - 1;
if (a[mid] < key)
first = mid + 1;
}
return -1;
}
}
posted on 2008-04-24 23:30
dreamingnest 阅读(43)
评论(0) 编辑 收藏 所属分类:
链表和栈（结）