「PHP」配列要素を見つけるために二分探索(バイナリサーチ)を行うアルゴリズムのプログラム

2014年7月9日

サンプルコード：

package OrderedArray;

/**
* 配列操作
*
*/
import java.util.Scanner;

class OrderedArray {
private int[] array;
private int nElems;

// コンストラクタ,順次付き配列のオブジェクトを生成
public OrderedArray(int max) {
// 配列のオブジェクトを生成
array = new int[max];
// 配列要素の初期値は0を設定
nElems = 0;
}

// 配列サイズを戻る
public int size() {
return nElems;
}

// 二分探索
public int BinarySearch(int searchKey) {
int lowBound = 0;
int highBound = nElems – 1;
int currentIndex;
while (true) {
currentIndex = (lowBound + highBound) / 2;
if (array[currentIndex] == searchKey)
// 配列のkey場所を返す
return currentIndex;
if (lowBound > highBound)
return nElems;
else {
if (array[currentIndex] < searchKey) {
lowBound = currentIndex + 1;
} else if (array[currentIndex] > searchKey) {
highBound = currentIndex – 1;
}
}
}
}

// 検索したい数字を入力
public int input() {
Scanner sc = null;
System.out.println(“検索したい数字を入力してください —>");
sc = new Scanner(System.in);
int searchKey = sc.nextInt();
sc.close();
return searchKey;
}

// 配列要素を表示する
public void display() {
for (int i = 0; i < nElems; i++) {
System.out.print(array[i] + " “);
}
}

// 挿入操作
public void insert(int value) {
int i;
for (i = 0; i < nElems; i++) {
if (array[i] > value) {
break;
}
}
for (int j = nElems; j > i; j–) {
// 配列要素は順次1桁を移動
array[j] = array[j – 1];
}

array[i] = value;
nElems++;
}

// 削除操作
public boolean delete(int value) {
boolean flag = false;
int j = BinarySearch(value);
if (j == nElems)
flag = false;
else {
for (int k = j; k < nElems; k++) {
array[k] = array[k + 1];
}
nElems–;
flag = true;
}
return flag;
}

};

public class OrderedArrayDemo {

public static void main(String[] args) {
int maxSize = 100;
OrderedArray arr = new OrderedArray(maxSize);
arr.insert(11);
arr.insert(32);
arr.insert(5);
arr.insert(26);
arr.insert(45);
arr.insert(88);
arr.insert(1);
arr.insert(9);
arr.delete(9);
arr.delete(88);
System.out.println(arr.size());
System.out.println(“———————“);
arr.display();
System.out.println();
int key = arr.input();
if (arr.BinarySearch(key) != arr.size()) {
System.out.println(“キーを見つけた!");
} else {
System.out.println(“キーが見つかりません!");
}

}
}