C++とPythonの違いについての質問
解決したいこと
プログラミングを勉強中の初心者です。C++にて実装した二分探索を、同じ発想でPythonにも実装しようとしたところ、エラーが発生しました。その理由がどうしてもわからず、質問させていただきます。
発生している問題・エラー
以前書いたC++での二分探索のコードが以下です。
二分探索
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> date(n);
for (int i=0;i<n;i++) {
cin >> date[i];
}
int target;
cin >> target;
int hi=n,lo=0,mid;
while (lo<=hi) {
mid=((lo+hi)/2);
if (target<=date[mid]) hi=(mid-1);
if (target>=date[mid]) lo=(mid+1);
//一致しなかった場合は範囲を半分に。
//一致した場合は、lo>hiとなりwhileが終了
}
int pos=(lo-1);//posは見つかった場合はそのレコードの場所を、見つからなかった場合は直前の場所を指し示す。
bool found=(lo==hi+2);//foundは見つかったかどうかのbool値
if (found) {
cout << "見つかりました" << endl;
cout << "場所は" << pos << "です" << endl;
} else {
cout << "見つかりませんでした" << endl;
cout << "targetの直前の場所は" << pos << "です" << endl;
}
}
このコードを、同じようにpythonで実装しようとして、次のコードを書きました。(こちらは関数であり、出力の様式が少し異なりますが、二分探索自体の挙動は同じであると思います)
二分探索
def search(ordered, item):
hi=len(ordered)
lo=0
while lo <= hi:
mid=((lo+hi)//2)
if item<=ordered[mid]:
hi=(mid-1)
if item>=ordered[mid]:
lo=(mid+1)
if lo==hi+2:
return lo-1
else:
return None
問題点
探索する元のリストが[1,2,3,4,5,6,7,8,9,10]で、探索する対象が11の時、C++では正しく動作したのに対して、pythonでは配列外を参照したことによるエラーが発生しました。そこで２行目のhi=len(ordered)を、hi=len(ordered)-1としたところ、正しく動作しました。
質問
なぜこのようなことが発生するのでしょうか。pythonとC++で配列の扱いに違いがあるのでしょうか。
また、hi=len(ordered)-1とすれば、このpythonのコードは適切に二分探索を行うことができますか。
終わりに
拙い文章とコードですが、ご教授いただけたら幸いです。
0
