我們來玩猜數字遊戲，1 ~ 100 中的整數，你必須猜中我腦海中的數字，而且我們必須在最少的布數內猜到答案，那麼你會怎麼猜呢？
答案很簡單，你一定會從 50 開始猜，如果沒猜中的話，太高你就會從 25 開始猜，太低你就會從 75 開始猜，以此類推，你每次操作的過程，你都會從中剖一半來猜測，其實你所使用的就是 Binary Search。
概念
二元搜尋 (Binary Search)：使用者個演算法之前，被搜尋的清單是需要先被排序過的，如果你要找的元素在清單內的話，二元搜尋會返回你該元素得位置編號，否則會回傳 -1 。
複雜度
- 時間複雜度： O(log n)
- 空間複雜度： O(1)
範例
Go
package main
import "fmt"
func binarySearch(list []int, target int) int {
low := 0
high := len(list) - 1
for low <= high {
mid := (low + high) / 2
if list[mid] == target {
return mid
} else if list[mid] < target {
low = mid + 1
} else {
high = mid - 1
}
}
return -1
}
func main() {
fmt.Println(binarySearch([]int{1, 2, 3, 4, 5}, 3)) // 2
fmt.Println(binarySearch([]int{1, 2, 3, 4, 5}, 6)) // -1
}
C#
class Algorithm
{
public static int binarySearch(int[] list, int target)
{
var low = 0;
var high = list.Length - 1;
while(low <= high)
{
var mid = (low + high) / 2;
if (list[mid] == target)
{
return mid;
}
if (list[mid] < target)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return -1;
}
public static void Main(String[] args)
{
Console.WriteLine(binarySearch(new int[] {1, 2, 3, 4, 5}, 3)); // 2
Console.WriteLine(binarySearch(new int[] {1, 2, 3, 4, 5}, 6)); // -1
}
}
歡迎到我的 Facebook Alan 的筆記本 留言，順手給我個讚吧！你的讚將成為我持續更新的動力，感謝你的閱讀，讓我們一起學習成為更好的自己。