开发者社区> 问答> 正文

二分查找如何定位左边界和右边界#前端面试

二分查找如何定位左边界和右边界#前端面试 不使用JS数组API,查找有序数列最先出现的位置和最后出现的位置

展开
收起
一月19 2020-05-23 12:52:37 1996 0
1 条回答
写回答
取消 提交回答
  • //递归查找
    function erfen_digui(arr, val, left = 0, right = arr.length - 1) {
            if (left > right) {
              return -1;
            }
            let cent = Math.floor((right + left) / 2);
            if (arr[cent] === val) {
              return `最终查找结果下标为${cent}`;
            } else if (arr[cent] > val) {
              right = cent - 1;
            } else {
              left = cent + 1;
            }
            return erfen_digui(arr, val, left, right);
          }
    //非递归查找
          function erfen_feidigui(arr, val) {
            let left = 0,
              right = arr.length - 1;
            while (left <= right) {
              let cent = left + Math.floor((right - left) / 2);
              if (arr[cent] === val) {
                return `最终查找结果下标为${cent}`;
              } else if (arr[cent] > val) {
                right = cent - 1;
              } else {
                left = cent + 1;
              }
            }
            return -1;
          }
    
    //左边界查找(查找第一个元素)
    function erfen_digui(arr, val, left = 0, right = arr.length - 1) {
            if (left > right) {
              return -1;
            }
            let cent = Math.floor((right + left) / 2);
            if (arr[cent] === val) {
              /****************改动点********************/
              if (arr[cent - 1] === val) {
                right = cent - 1;
              } else {
                return `最终查找结果下标为${cent}`;
              }
              /*****************************************/
            } else if (arr[cent] > val) {
              right = cent - 1;
            } else {
              left = cent + 1;
            }
            return erfen_digui(arr, val, left, right);
          }
    
    // 二分查找右边界(查找最后一个元素)
    function erfen_digui(arr, val, left = 0, right = arr.length - 1) {
            if (left > right) {
              return -1;
            }
            let cent = Math.floor((right + left) / 2);
            if (arr[cent] === val) {
              /****************改动点********************/
              if (arr[cent + 1] === val) {
                left = cent + 1;
              } else {
                return `最终查找结果下标为${cent}`;
              }
              /*****************************************/
            } else if (arr[cent] > val) {
              right = cent - 1;
            } else {
              left = cent + 1;
            }
            return erfen_digui(arr, val, left, right);
          }
    
    2020-05-23 14:39:44
    赞同 展开评论 打赏
问答排行榜
最热
最新

相关电子书

更多
阿里云技术面试红宝书 立即下载
超全算法笔试-模拟题精解合集 立即下载
程序员面试宝典 立即下载