---
title: 二進制
tags: math, calculation
---

# 二進制 Binary

最普遍用途是將10進制轉換成2進制的方式表示，

10進制可以是這樣子看的：
$157387=1×10^5+5×10^4+7×10^3+3×10^2+8×10^1+7×10^0$
$=100000+50000+7000+300+80+7$

比如說，將275從十進位轉成二進位會變成$(100010011)_2$，
將其寫開，亦可以表示成$1×2^8+1×2^4+1×2^1+1×2^0$
又或是用內積的方式來寫
$(1,0,0,0,1,0,0,1,1)\cdot(2^8,2^7,2^6,2^5,2^4,2^3,2^2,2^1,2^0)$

因為變換的是進位，基本上利用進位關係就可以簡單證明任意十進位數皆可以表示成二的次方和

# 分治法 Divide & Conquer

分治法的核心概念是在於藉由切小子問題再進行比較，其處理子問題之時間總和可以比原問題還要來得小，最典型的問題是二分搜尋法

## 二分搜尋法(Binary Search)

對一個長度為 $N$ 的已排列數組，可以用 $O(\log N)$ 的時間找目標數字的位址