programmercarl——数组——二分查找

二分查找,在经过:

  • 34——https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
  • 35——https://leetcode-cn.com/problems/search-insert-position/
  • 69——https://leetcode-cn.com/problems/sqrtx/
  • 367——https://leetcode-cn.com/problems/valid-perfect-square/

的学习之后,我的二分想法如下:

int left, right, mid;
while (left <= right) {
    mid = left + (right - left)/2;
    if (mid < target) {
        left = mid + 1;
    }else if (mid > target) {
        right = mid - 1;
    }else {
        return mid;
    }
    return -1;
}

同时,以下有两个二分算法的注意事项:

  1. 使用二分,数组必须是非降序的
  2. 使用二分之前,必须将问题转化为在序列中寻找特定数值的数,或者在特定问题中的“比较”方式,即定义好所需的compareTo()
上一篇:problems_kudu


下一篇:二维数组双指针搜索正确性