『アルゴリズムを学ぼう』より、 a) (a ** k) % m を求める b) vが配列vsに入っているかを検索する

gistfile1.java

int powmod(int a, int k, int m){// a^k をm で割った余りを求める
  long t=1;
  for (int i=1; i<k; ++i) // loopして
    t = (t * a) % m;
  return (int)t;
}

int powmod(int a, int k, int m){// kが巨大な場合を考えて、再帰的にkを分割
  if (k == 0)
    return 1;
  long t = powmod(a, k/2, m);// 2つに分割した結果
  if (k % 2  == 1)
    t = t * a % m;
  return (int) t;
}

// --------
// 配列から値を検索する
public boolean contains(int v, int[] vs){
  for (int i=0; i<vs.length; i++){
    if (vs[i] == v) return true;
  }
  return false;
}


// 二分探索
// a.中央の数を見る
// b1.検索数vより小さいなら、左を検索
// b2.検索数vより大きいなら、右を検索
// b3.一致するなら、indexを返す

// 再帰使わなくても大丈夫ですよ？

public boolean contains(int v, int[] vs){
	if (vs.length == 0) return false;
	
	int left = 0, right = vs.length;
	while (left + 1 < right) {
		//int mid = (left + right) / 2;
		int mid = left + (right - left) / 2;
		if (v < vs[mid])
			right = mid;
		else
			left = mid;
	}
	return v == vs[left]; //該当しなかったら、外れのleftが残っている
}

p35. 計算量の話。

• ? ふたつめのpowmodがO(logN)になる筋道。