1027-二分查找

冷不防 2022-11-20 08:24 145阅读 0赞

在这里插入图片描述
解题思路：
根据二分法的算法思想，需要使用左右两个下标寻找得到的值，在本题中，第一次二分就能得到最后的值，但是输出的index是3，因此需要从找到的位置的左指针处+1；

  1. class Solution {
  3. public:
  4.     /**
  5.      * 二分查找
  6.      * @param n int整型 数组长度
  7.      * @param v int整型 查找值
  8.      * @param a int整型vector 有序数组
  9.      * @return int整型
  10.      */
  11.     int upper_bound_(int n, int v, vector<int>& a) {
  13.         // write code here
  14.         int right = n-1, left = 0;
  15.         while(left <= right)
  16.         {
  18.             int mid = (left + right) / 2;
  19.             if(a[mid] > v)
  20.             {
  22.                 right = mid - 1;
  23.             }else if(a[mid] < v)
  24.             {
  26.                 left = mid + 1;
  27.             }else
  28.                 right = mid - 1;
  29.         }
  30.         return left + 1;
  31.     }
  32. };

发表评论

表情：
评论列表 （有 0 条评论，145人围观）

还没有评论，来说两句吧...

相关阅读

    相关 二分查找

    二分查找可以说是在经典不过的查找算法了，比如JAVA的库函数里，就有相应的代码实例。如下写出两个版本的二分查找，非递归和递归的 非递归的 public int bi

    系统管理员系统管理员/ 0 赞/ 151 阅读

    相关 查找——二分查找

    基本思想 二分查找是建立在有序顺序表基础上的！步骤如下： 1.      将表中间位置记录的关键字与给定K值进行比较，若两者相等，则查找成功。 2.    

    蔚落蔚落/ 0 赞/ 509 阅读