paiza.ioで二分探索法のアルゴリズムを書いてTimeoutになる。

Question

前提・実現したいこと

配列内のデータ「31」からTimeoutになるのと、配列内に無いデータを入力するとTimeoutになるのですが、目的のデータが配列のどこにあるのかを出力したいです。

発生している問題・エラーメッセージ

Timeout

エラーメッセージ

エラーメッセージは無いです。

該当のソースコード

ソースコード
class Main{
 static int binSearch(int[] array,int key){
   int head=0;
   int tail=6;

   do{
      int center=(head+tail)/2;
      if(array[center]==key){
        return center;
      }else if(array[center]<key){
        head=center++;
      }else{
        tail=center--;
      }
     }while(head<=tail);
    return -1;
 }
 public static void main(String[] args){
  int[] array={11,13,17,19,23,29,31};
  int target=31;

  int index=binSearch(array,target);

  if(index !=-1){
   System.out.println(index+"番目の要素が一致");
  }else{
   System.out.println("見つかりませんでした");
  }
 }
}

試したこと

ここに問題に対して試したことを記載してください。

補足情報（FW/ツールのバージョンなど）

https://paiza.io/projects/RndYNPPLtbJt55OwdCDALg

Comments

[maisumakun]

第三者に聞いていい問題なのでしょうか？

[whitehorse85921]

仕事じゃないので大丈夫です。

[dice142]

仕事かどうかではなく、Paizaの利用規約に引っかかるかどうかですね。
Paizaの利用規約の禁止行為を確認してください。

[whitehorse85921]

paizaの問題じゃないですよ。paiza.ioはネット上でコードが書けるサービスです。

[dice142]

あ、失礼しました。
paiza.ioでpaizaの問題を解いていての質問かと早とちりしました。

[m.ts10806]

動作確認できるpaiza.ioのURL貼ってもらったほうが良いですね。
「ソースコード」だけ除いたコードだとエラー出ますし。
https://paiza.io/projects/RndYNPPLtbJt55OwdCDALg

[whitehorse85921]

大丈夫です。

[maisumakun]

何かの問題だと思っていました。失礼しました。

[m.ts10806]

とりあえずスペルミスはありますね
intdex
↓
index

[whitehorse85921]

前後してしまってすみません。アドバイスありがとうございます。

[m.ts10806]

質問は編集できますので、ご自身が試されたpaiza.ioの実行結果で得られるURLを質問本文にご提示ください。

[whitehorse85921]

時間がかかってすみません。このサイト久しぶりに使ったので、編集に時間がかかりました。

[m.ts10806]

解決されたようですね。
ただ、回答していない私が言うのもなんですが、今回は「結局どのようにして解決に至ったか」は気になります。もしかしたら回答者の意図通りの対応ではないかもしれないし。
そのあたりは詳細をコメントしてあげてください。
https://teratail.com/help/question-tips#questionTips4-2

[whitehorse85921]

分かりました。詳細にコメントしてみます。アドバイスありがとうございます。

Answer 1

インクリメントやデクリメントが後置であるため、headとtailが隣り合わせの状態で見つからない場合、そこからheadもtail全く動かなくなります。インクリメント、デクリメントを前置にするか、+1,-1で普通に式を書くかする必要があります。

Comments

[whitehorse85921]

ありがとうございます！できました。

[whitehorse85921]

最初は、メソッドを使わずにwhile文とif-else文だけで書いていました。
でも、それでは配列にデータがなかった時に「見つかりませんでした」と出力できないことに悩みました。それで、ネットや本を調べてみてメソッドを作れば、配列にデータがないときの処理ができると分かりました。それで配列内に目的のデータを探すメソッドを書き、出力したのですがインデックスが5に入っているデータが出てこないことと、配列内にないデータが「見つかりませんでした」と出力されないことに悩みました。そこでswordoneさんの仰ったように書いたら動いたのですが、なぜ、動いたか分かりませんでした。そこでググってみて「前置」の場合は式ないしメソッドの評価を行う前にインクリメントやデクリメントを行うというのを見つけて一時間以上考えて、ググったのですが分からなかったので、詳細なコメントができるまで少し時間をください。すみません。

Answer 2

head、tail、centerの値をループ毎に出力してみて、動作を追ってみてはいかがでしょうか。

int i = 0;
do{
    int center=(head+tail)/2;
    System.out.printf("%d, %d, %d\n", head, center, tail);
    ...

    if(i++ > 20) break;
} while(head<=tail);

想定どおりに動作していない筈です。

例えば、

head=center++;

この書き方だとheadにはcenterの値がそのまま代入されています。

コメントを受けて：実験

class Main {
    public static void main(String[] args) {
        {
            // ただの足し算
            int a = 10;
            int b;
            
            b = a + 1;
            System.out.printf("a=%2d, b=%2d\n", a, b);  // => a=10, b=11
        }
        {
            // 前置インクリメント
            int a = 10;
            int b;
            
            b = ++a;
            System.out.printf("a=%2d, b=%2d\n", a, b);  // => a=11, b=11
        }
        {
            // 後置インクリメント
            int a = 10;
            int b;
            
            b = a++;
            System.out.printf("a=%2d, b=%2d\n", a, b);  // => a=11, b=10
        }
    }
}

• b = a + 1

aの値は勝手に更新されない。bにはaに1を足した数が代入される。

• b = ++a

aの値は1だけ大きくなり、その値がbに代入される。

• b = a++

aの値がbに代入された後、aの値は1だけ大きくなる。

Comments

[whitehorse85921]

ありがとうございます。

[whitehorse85921]

動作を追ってみました。center++やcenter--だと、探したいデータが31のとき、インデックス番号が5，5，6で止まったままで動きませんでした。++centerや--centerの時は、0, 3, 6　4, 5, 6　6, 6, 6となりました。なぜcenter++やcenter--だと動かないのか一時間以上ググって考えましたが分かりませんでした。すみません。

[whitehorse85921]

きめ細やかにありがとうございます。
前置と後置では、加算、減算するタイミングがそれぞれ違うのですね。
center++;だと、centerがheadに代入された後にcenterの値が1だけ大きくなるので、例えば、探したい目的のデータのあるインデックスが5の場合、後で加算されてからではタイミングが遅いので、headにcenterの値5がそのままなのかなと思いました。間違って解釈していたらすみません。

[LouiS0616]

ご提示のコードでは毎周centerを上書きしているので、
b = center++ は b = center に、 b = ++center は b = center + 1 に置き換えても同じように動作します。

[whitehorse85921]

tail=center--;もtail=centerになるのですね。
ありがとうございます。