[CS50] week 0 -  2進数と二分探索

# 初めに
今回はデータ構造とアルゴリズムの基礎知識を深めたいと思い、主に **CS50 Lectures 2016** の映像を通して考えていることと学んだことを記録していきたいです。

https://youtube.com/playlist?list=PLhQjrBD2T382VRUw5ZpSxQSFrxMOdFObl

https://www.youtube.com/watch?v=NZxALvNlF-8&list=PLhQjrBD2T383f9scHRNYJkior2VvYjpSL

https://www.youtube.com/@cs50forjapanese30/videos

（今回の文章はメモというより多くは初心者である自分の自問自答です。）

# week 0
## Binary & ASCII & RGB

https://www.geek-computer.com/wiki/why-do-computers-use-binary-numbers

データ構造やアルゴリズム、コンピューターサイエンスすべてのベースと言ってもいい2進数は、どうして2進数なのか？と、10進数しか使ったことのない初心者の私によくある質問です。

**どうして10進数を使わず2進数をベースしたのか、2進数のメリットは何だろうか。**

計算の速さからすれば2を基数として、0と1、false/true、いいえとはい、一つの桁のなかでは2つの結果しかありません。10進数だと一つの桁が毎回0-9の計算が必要です。

確かに一つの桁には10種の表現ができて、格納するものが増えるかもしれませんが、データを格納する一つの空間（ビット数、単位）が8bitだと毎回10の8乗の計算量が必要なので、効率が悪いと言っていいでしょう。

そして一つの単位（8bit/16bit...）空間の大きさが、格納できる表現を影響はする（超過した表現を失くしたりとか）が、これは2進数にしても10進数にしても同じです。

探索の正確性からすれば二分木のように、左か右、一意の位置にしかたどり着けない仕組みになりますね。（この点では10進数も同じだが、正しい座標にいくまで複雑な計算がなくなるということが言いたいです。）

**そもそも情報とは何でしょう。格納空間との関連性は？**

情報（Information）処理の「情報」という言葉がとても気になります。自分の認識ではそれが文字や色など、事実伝達するために組み合わせたものです。

正式表現を学んで初めて「コードポイント／コードユニット」という言葉に触れて、人間の言葉を正しく伝達・反映するには、一意の数学表現（コードユニットは特にUTF-16に指して2バイト表現）を通して文字と対応関係するという文字コード体系を作り、事実伝達をするのを知りました。

知識まだまだ浅い自分は、情報処理とは固定された空間（バイト）で数学表現を通して事実伝達の手法を具現化していくのではないかと思っています。（正式に勉強したことのない、ただ一人の学習者としての感想で書くつもりですが、誤解を招いてしまったら申し訳ございません。）

なので速さも正しさも発揮できる2進数がベースになったのは、とても合理的だと思います。

（RGB の方は赤、緑、青を画面のピクセルごと 8*3 = 24bit で表現していくのが画像そしてビデオ...映像の中とてもわかりやすく説明されているのでスキップしました。）

## A Good Algorithm
二分探索：大小関係から要素（値）が中央値より左か右にあるかを判断し、不要な片側の要素を切り捨てながら検索する。
- 要素が事前にソートされる必要がある。
- 全体要素の大小関係の確立が必要。

### Finding Mike Smith
映像のトピックを用いて JavaScript で二分探索を書いてみました。
```js
// charCode
const start = 'A'.codePointAt(0);
const end = 'Z'.codePointAt(0);

function findTarget(str) {
  const target = str.codePointAt(0);
  if (target < start || target > end) return;

  let middle = (end - start + 1) / 2;
  let tempInterval = start + middle;
  let complete = false;
  let counter = 0;

  while (!complete) {
    if (target > tempInterval) {
      tempInterval = tempInterval + Math.ceil(middle / 2);
      counter++;
    } else if (target < tempInterval) {
      tempInterval = tempInterval - Math.ceil(middle / 2);
      counter++;
    } else {
      complete = true;
      counter++;
      return `We found ${str} at ${counter} times`;
    }
    middle = Math.ceil(middle / 2);
  }
}

let name = 'Mike Smith';
// console.log(name.codePointAt(0)); // 77
console.log(findTarget(name));
// We found Mike Smith at 4 times

let randomAlphabet = Math.floor(Math.random() * (end - start + 1) + start);
console.log(findTarget(String.fromCharCode(randomAlphabet)));
// We found J at 5 times
```
照合が配列に変えても手順は変わらないです。
```js
// array
const alphabetArr = [
  'A',
  'B',
  'C',
  'D',
  'E',
  'F',
  'G',
  'H',
  'I',
  'J',
  'K',
  'L',
  'M',
  'N',
  'O',
  'P',
  'Q',
  'R',
  'S',
  'T',
  'U',
  'V',
  'W',
  'X',
  'Y',
  'Z',
];

const start = 0;
const end = alphabetArr.length - 1;

function findTarget(str) {
  const target = str[0];
  if (target < alphabetArr[start] || target > alphabetArr[end]) return;

  let middle = (end - start + 1) / 2;
  let tempInterval = start + middle;
  let complete = false;
  let counter = 0;

  while (!complete) {
    if (target > alphabetArr[tempInterval]) {
      tempInterval = tempInterval + Math.ceil(middle / 2);
      counter++;
    } else if (target < alphabetArr[tempInterval]) {
      tempInterval = tempInterval - Math.ceil(middle / 2);
      counter++;
    } else {
      complete = true;
      counter++;
      return `We found ${str} at ${counter} times`;
    }
    middle = Math.ceil(middle / 2);
  }
}

let randomAlphabet = Math.floor(Math.random() * (end - start + 1));
console.log(findTarget(alphabetArr[randomAlphabet]));
// We found X at 5 times
```

https://visualgo.net/en/bst

### O(n) & O(n^2) & O(log n)
- O(n)：一重ループ。
- O(n^2)：二重ループ。（多重ループ→O(n^n)）
- O(log n)：二分探索法。

https://note.com/strictlyes/n/n82d0a3874256