第三章：二分查找基础

课程_算法系统课 0 285 免费

二分查找两种写法

闭区间[l, r]

闭区间需要注意的点：
1、当 l = = r 时，区间是有意义的，所以 while(l <= r)
2、更新 r 时，如果 arr[mid] > target，则 mid 不可能是我们要找的数，所以 r = mid – 1。

下面是三种代码实现（其他语言过两天更新）

Java

// 寻找 target 在数组的下标
int find(int[] arr, int target){
  int l = 0;
  int r = arr.length - 1;//注意点
  // l == r  有意义的
  while(l <= r){//注意点
    //int mid = (l + r) /2;// 存在数值溢出
    int mid = l + (r - l) / 2;
    if(arr[mid] > target){
      r = mid - 1;.// 注意点
    } else if(arr[mid] < target){
      l = mid + 1;
    } else {
      return mid;
    }
  }
}

C++

Python

左闭右开

闭区间需要注意的点：
1、当 l = = r 时，区间是没有意义的，因为 r 不可能是我们要找的数，所以 while(l < r)
2、更新 r 时，r 是不能 r = mid – 1 的，因为 r 不能成为目标数，所以 r = mid;

// 寻找 target 在数组的下标
int find(int[] arr, int target){
  int l = 0;
  int r = arr.length;
  // l == r无意义
  while(l < r){
    int mid = (l + r) /2;
    if(arr[mid] > target){
      r = mid;// 不能 r = mid - 1;
    }else if(arr[mid] < target){
        // 视频中写错了，视频中写成了 l = mid - 1;
      l = mid + 1;
    }else {
      return mid;
    }
  }
}

发表评论取消回复

后才能评论