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

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

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

// 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,这样当 lohi 相邻时,二分查找就会退出循环,避免 lo 大于 hi 的情况发生。跳出循环后,我们还需根据题目要求比较 lohi 索引下的数组值和目标值是否相符,返回题目要求的结果。
  • 我觉得这个模板最大的好处就在于能给初学者一个比较清晰的思路,不会因 lohi 的索引混乱产生思路的混乱,造成死循环的产生。
  • 后续博文涉及的二分查找算法题我都将用此模板进行解答。
  • 参考:YouTube - basketwang
本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!