基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

令和5年度問題  (参照；基本情報技術者 平成19年秋期試験問14）
問13
二分探索

例
   1  2  3  4  5  6  7  8  9
   11 12 13 14 15 16 17 18 19

 x←整数入力データ
(ここでは13（小さいデータ）と17(大きいデータ）します)
 lo←1
 hi←9

 do
 k←(lo+hi)/2
     (1+9)/2=5

  if(A[k]=x)
  "xは存在する" 

  elseif(A[k]<x)
          15<17
  lo←k+1
   6  5+1

  elseif(A[k]>x)
          15>13

  hi←k-1
   4  5-1

だから
 a lo←k+1
 b hi←k-1


といった理解で良いのかお聞きしました
よろしくお願いいたします。

この投稿は投稿者により削除されました。(2024.01.19 22:44)

ご質問の答えになっているかわかりませんが、
二分ではなく三分で考えるとこの問題は分かりやすいと思います。

問題：昇順に整列されたn個のデータが格納されている配列Aからデータxを探し出す。

配列A[1]～A[n]
1→lo
n→hi

とすると探索範囲は、A[lo]～A[hi]になります。

(lo+hi)/2→k  配列のだいたい真ん中あたり
としたとき、探索範囲が

＞グループ    A[lo]～A[k-1]
A[k]グループ  （1つですがグループ）
＜グループ    A[k+1]～A[hi]

の3つのグループに分かれたと考えます。

A[k]:xでxがどのグループになるか判断します。
A[k]>xならば、＞グループ  次の探索範囲はA[lo]～A[k-1}に絞られます。
k-1をhiにして(lo+hi)/2→kに戻ります。

A[k]=xならば、A[k]グループ  xは存在する  終了。

A[k]<xならば、＜グループ  次の探索範囲はA[k+1]～A[hi}に絞られます。
k+1をloにして(lo+hi)/2→kに戻ります。

途中で、lo>hi になったら探索範囲が決められないので、xは存在しない  終了。
となります。

>boyonboyonさん
詳しい解説ありがとうございました。
二分探索には腑に落ちない点もをもっていたので分かりました

A[k]<xならば、＜グループ  次の探索範囲はA[k+1]～A[hi}に絞られます
その部分が紙に書いても何かいまいち理解出来ずにいました