二分查找 | 二分查找的一种推荐写法

二分查找是刷题者必知必会的一个算法，写法有很多种，对于初学者来说，如果没有记住一种固定写法，很容易不同写法混淆，造成错误。

这是我写二分查找算法题时固定的模板：

// int[] nums[] -- array
// int target -- the num we want to find
// return the index of target if found
int len = nums.length;
int lo = 0;
int hi = len - 1;
while (lo + 1 < hi) { // *key
    int mid = (hi - lo) / 2 + lo; // Avoiding overflow
    if (nums[mid] == target) {
        return true;
    } else if (nums[mid] <target) {
        lo = mid;
    } else {
        hi = mid;
    }
}

if (nums[hi] == target || nums[lo] == target) {
    return true;
}

return false;

• 如果你对二分查找不太熟悉，可以查阅资料自行了解，本文不再赘述。
• 这个写法的关键在于将 while-loop 的条件设定为 lo + 1 < hi，这样当 lo 和 hi 相邻时，二分查找就会退出循环，避免 lo 大于 hi 的情况发生。跳出循环后，我们还需根据题目要求比较 lo 和 hi 索引下的数组值和目标值是否相符，返回题目要求的结果。
• 我觉得这个模板最大的好处就在于能给初学者一个比较清晰的思路，不会因 lo 和 hi 的索引混乱产生思路的混乱，造成死循环的产生。
• 后续博文涉及的二分查找算法题我都将用此模板进行解答。
• 参考：YouTube - basketwang

本作品采用《CC 协议》，转载必须注明作者和本文链接