簡介
你偶然遇上了一群既是數學家、也是創作歌手的人。
他們為每一個自己喜歡的數字寫了一首歌，而你可以想見，他們喜歡的數字還真不少（例如 0、73 或 6174）。
你很想知道自己最喜歡的數字是哪一首歌，但歌這麼多，要找到正確的那一首可得花上一段時間。
幸好，他們把歌曲整理成一份依標題排序的播放清單，而標題就是歌曲所描寫的那個數字。
你發現，只要用二分搜尋演算法，就能依標題快速找到想聽的那首歌。
說明
你的任務是實作二分搜尋演算法。
二分搜尋演算法會反覆把陣列切成兩半，只留下包含我們要找的項目的那一半，藉此在陣列中找到項目。
它可以讓我們快速縮小項目可能出現的位置，直到找到它，或是排除所有可能的位置。
這個演算法的流程如下：
- 找出_已排序_陣列中間的元素，並拿它和我們要找的項目比較。
- 如果中間的元素就是我們要找的項目，那就完成了！
- 如果中間的元素比我們的項目大，就可以排除那個元素以及它之後的所有元素。
- 如果中間的元素比我們的項目小，就可以排除那個元素以及它之前的所有元素。
- 如果陣列中的每個元素都被排除了，就代表這個項目不在陣列裡。
- 否則，就對陣列中還沒被排除的部分重複同樣的流程。
來看一個例子：
假設我們要在下面這個已排序的陣列中尋找數字 23：[4, 8, 12, 16, 23, 28, 32]。
- 我們先拿 23 和陣列中間的元素 16 比較。
- 因為 23 大於 16，我們可以排除陣列的左半部，剩下
[23, 28, 32]。
- 接著，我們拿 23 和新的中間元素 28 比較。
- 因為 23 小於 28，我們可以排除陣列的右半部：
[23]。
- 我們找到目標項目了。
行為
在測試案例中，你的解法行為應該與 Julia 內建的searchsorted函式一致。
這代表你要回傳的並不是你在陣列中找到的第一個相符元素的索引，而是一個範圍；這個範圍的下界是陣列中第一個相符元素的索引，上界則是最後一個相符元素的索引。
不過，為了簡化你的解法，你可以假設目標元素不會重複，只有多重相符的加分任務測試集例外。
如果要搜尋的項目不在陣列中，你必須回傳一個空範圍，其下界是該項目可以插入已排序陣列中的索引位置。空範圍是指上界小於下界的任何範圍。
更多細節請參閱searchsorted函式的說明文件與範例：
searchsorted(a, x; by=<transform>, lt=<comparison>, rev=false)
Return the range of indices of a which compare as equal to x (using binary
search) according to the order specified by the by, lt and rev keywords,
assuming that a is already sorted in that order.
Return an empty range located at the insertion point if a does not contain
values equal to x.
See also: insorted, searchsortedfirst, sort, findall.
Examples
julia> searchsorted([1, 2, 4, 5, 5, 7], 4) # single match
3:3
julia> searchsorted([1, 2, 4, 5, 5, 7], 5) # multiple matches
4:5
julia> searchsorted([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
3:2
julia> searchsorted([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
7:6
julia> searchsorted([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
1:0
加分任務
- 擴充你的解法，支援關鍵字引數
by、lt和rev，讓by指定套用到陣列中所有元素的轉換，lt指定比較方式，而rev指定陣列是否以反向排序。使用這些參數時，你必須假設陣列已經依照這些參數排序過。更多細節請參閱sort的說明文件。
- 支援目標元素會重複的陣列（找出目標元素比較結果相等的第一個與最後一個索引）。
