秩序配列と二分検索
3071 ワード
//OrderArray.java
public class OrderArray {
private int[] a;
private int nElements;
public OrderArray(int max) {
a = new int[max];
nElements = 0;
}
public void insert(int element) {
if (nElements == a.length) {
System.out.println("can't insert, array is full.");
return;
}
int j;
for (j = 0; j < nElements; j++)
if (a[j] > element)
break;
int k;
for (k = nElements; k > j; k--)
a[k] = a[k - 1];
a[j] = element;
nElements++;
}
/**
*
*
* @param element
* @return
*/
public int binarySearch(int element) {
int lowerBound = 0;
int upperBound = nElements - 1;
int binaryBound;
while (true) {
binaryBound = (lowerBound + upperBound) / 2;
if (a[binaryBound] == element) //
return binaryBound;
else if (lowerBound > upperBound) // 404
return -1;
else if (a[binaryBound] > element)
upperBound = binaryBound - 1;//
else
lowerBound = binaryBound + 1;//
}
}
public boolean delete(int element) {
int j = binarySearch(element);
if (j == -1)
return false;
int k;
for (k = j; k < nElements - 1; k++)
a[k] = a[k + 1];
a[nElements - 1] = 0;
nElements--;
return true;
}
public void display() {
StringBuffer sb = new StringBuffer();
sb.append("[");
int j;
for (j = 0; j < a.length; j++) {
sb.append(a[j] + ",");
}
sb.deleteCharAt(sb.length() - 1);
sb.append("]");
System.out.println(sb.toString());
}
}
//Main.java
public class Main {
public static void main(String[] args){
OrderArray orderArray = new OrderArray(10);
orderArray.insert(111);
orderArray.insert(888);
orderArray.insert(333);
orderArray.insert(222);
orderArray.insert(666);
orderArray.insert(555);
orderArray.insert(444);
orderArray.insert(999);
orderArray.insert(777);
orderArray.insert(1111);
orderArray.insert(2222);
orderArray.display();
System.out.println(orderArray.binarySearch(88));
System.out.println(orderArray.binarySearch(1000));
System.out.println(orderArray.delete(333));
System.out.println(orderArray.binarySearch(999));
System.out.println(orderArray.delete(555));
orderArray.insert(555);
orderArray.insert(555);
orderArray.display();
}
}
出力結果:
can't insert, array is full.
[111,222,333,444,555,666,777,888,999,1111]
-1
-1
true
7
true
[111,222,444,555,555,666,777,888,999,1111]