二分查找的思路

先找到那個(gè)有序序列的中間元素mid，然后拿它和要找的元素進(jìn)行比較，就可以初步判斷元素所在范圍，既然查找范圍已確定，自然該范圍之外的元素就可以不用再查找了，然后按照上面的步驟反復(fù)查找下去。

折半查找要求查找表進(jìn)順序儲(chǔ)拼且按關(guān)鍵字有序排列，因此對(duì)表進(jìn)行元素的插入和刪除時(shí)，需要移動(dòng)大量的元素，所以折半查找適用于表不易變動(dòng)，且又經(jīng)常進(jìn)行查找的情況。

前提條件：查找的序列必須有序

時(shí)間復(fù)雜度：O（logn）

二分查找一般應(yīng)用于滿足某條件的第一/最后一個(gè)數(shù)，查找最大/最小值的情況。

此外，在二分查找中，還存在左右邊界的問(wèn)題。

比如查找的是7，有重復(fù)的倆個(gè)7，由此需要?jiǎng)澐肿笥疫吔纭?/p>

bSearchL和bSearchR的最大區(qū)別就是mid這一條件的設(shè)置，前者將區(qū)間[l, r]劃分成[l, mid]和[mid + 1, r]，后者將區(qū)間[l, r]劃分成[l, mid - 1]和[mid, r]。而(l+r)>>1和(l+r+1)>>1的區(qū)別在于，(l+r+1)>>1進(jìn)行了向上取整。

至于最后返回值的時(shí)候，返回l和r皆是可行的，因?yàn)樽詈笠欢?r==l，下面的l,r寫法只是為了方面區(qū)分。

而同時(shí)獲取左右邊界就是數(shù)的范圍問(wèn)題了。

數(shù)的范圍問(wèn)題

給定一個(gè)按照升序排列的長(zhǎng)度為 n 的整數(shù)數(shù)組，以及 q 個(gè)查詢。

對(duì)于每個(gè)查詢，返回一個(gè)元素 k 的起始位置和終止位置（位置從 0 開(kāi)始計(jì)數(shù)）。

如果數(shù)組中不存在該元素，則返回 -1 -1。

數(shù)的范圍的過(guò)程

1.查找左邊界

2.判斷左邊的元素是否存在（如果左邊界查不到，說(shuō)明這個(gè)數(shù)不存在序列中，直接返回，如果左邊界能查詢到，說(shuō)明這個(gè)數(shù)存在于序列中，那就一定存在右邊界）

3.根據(jù)判斷結(jié)果查找并返回返回右邊界

偷懶，今天沒(méi)怎么進(jìn)行學(xué)習(xí)。