前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >二分搜索框架

二分搜索框架

作者头像
艳龙
发布2021-12-16 17:53:19
1850
发布2021-12-16 17:53:19
举报
文章被收录于专栏:yanlongli_艳龙yanlongli_艳龙

注意事项

-搜索区间需要特别留意:[左开、右开] 还是 [左开、右闭)

  • while 终止 是否需要带 =号, 区间与 最开始确定的搜索区间
二分搜索框架
代码语言:javascript
复制
    int binarySearch(int num[], int target) {
        
        // 注意 二分搜索的区间是 [左开,右开]
        int left = 0;
        int right = num.length - 1;
        
        // 所以这里的终止条件是 left > right
        while (left <= right) {
            // (left + right ) / 2 和 left + ((right - left ) / 2) 结果相同
            // left 和 right 太大, (left + right ) / 2 可能溢出
            int mid = left + ((right - left ) / 2);
            if (mid == target) {
                return mid;
            } else if (mid > target) {
                right = mid - 1;
            } else if (mid < target) {
                left = mid + 1;
            }
        }
        
        return -1;
    }
左侧二分搜索边界
代码语言:javascript
复制
    int left_bound(int num[], int target) {
        
        // 注意 二分搜索的区间是 [左开,右开]
        int left = 0;
        int right = num.length - 1;
        
        // 所以这里的终止条件是 left > right
        while (left <= right) {
            // (left + right ) / 2 和 left + ((right - left ) / 2) 结果相同
            // left 和 right 太大, (left + right ) / 2 可能溢出
            int mid = left + ((right - left ) / 2);
            if (mid == target) {
                right = mid - 1;  // 找到后,不返回,收缩右侧边界,继续搜索
               // return mid;  
            } else if (mid > target) {
                right = mid - 1;
            } else if (mid < target) {
                left = mid + 1;
            }
        }
        if (left >= num.length || num[left] != target) {
                return -1;
        } 
        return left;
    }
右侧二分搜索边界
代码语言:javascript
复制
    int right_bound(int num[], int target) {
        
        // 注意 二分搜索的区间是 [左开,右开]
        int left = 0;
        int right = num.length - 1;
        
        // 所以这里的终止条件是 left > right
        while (left <= right) {
            // (left + right ) / 2 和 left + ((right - left ) / 2) 结果相同
            // left 和 right 太大, (left + right ) / 2 可能溢出
            int mid = left + ((right - left ) / 2);
            if (mid == target) {
                left = mid + 1;  // 找到后,不返回,收缩左侧边界,继续搜索
               // return mid;  
            } else if (mid > target) {
                right = mid - 1;
            } else if (mid < target) {
                left = mid + 1;
            }
        }
        if (right < 0 || num[right] != target) {
                return -1;
        } 
        return right;
    }
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021/5/10 上,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 注意事项
    • 二分搜索框架
      • 左侧二分搜索边界
        • 右侧二分搜索边界
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档