Binary Search

板上看到 Binary Search 的問題:Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken

簡單來說就是 int 能處理的數字不夠,以他給的例子中:

6:        int mid = (low + high) / 2;

當 low + high > INT_MAX 時就會炸掉,所以在這篇文章裡給了一些解法:

6:        int mid = low + ((high - low) / 2);

或是:

6:        mid = ((unsigned) (low + high)) >> 1;

果然是在大單位裡面才會遇到的 bug XD

Leave a Comment