【面试必刷TOP101】面试官:如何实现二分查找?

简介: 【面试必刷TOP101】面试官:如何实现二分查找?

二分查找-I


描述(题目简单) 考点:二分查找

请实现无重复数字的升序数组的二分查找

给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标(下标从 0 开始),否则返回 -1

数据范围:0 ≤len(nums)≤2×10^5 , 数组中任意值满足 |val| ≤10^9

进阶:时间复杂度 O(log n),空间复杂度 O(1)

微信图片_20221013132925.png

解题思路:


step 1:从数组首尾开始,每次取中点值。

step 2:如果中间值等于目标即找到了,可返回下标,如果中点值大于目标,说明中点以后的都大于目标,因此目标在中点左半区间,如果中点值小于目标,则相反。

step 3:根据比较进入对应的区间,直到区间左右端相遇,意味着没有找到。

微信图片_20221013132937.gif

题解:

//语言①: c
int search(int* nums, int numsLen, int target ) {
    if (numsLen <= 0)return -1;
    int low = 0, high = numsLen - 1;                    //初始化双指针
    int mid = (low + high) / 2;
    while (target != nums[mid] &&
            low <= high) {        //若当前mid值不为查找值,更新查找区域。
        if (target > nums[mid]) {
            low = mid + 1;
            mid = (low + high) / 2;
        } else {
            high = mid - 1;
            mid = (low + high) / 2;
        }
    }
    if (low > high)return -1;
    else return mid;
}
//语言②: JavaScript
function search(nums, target) {
  // write code here
  let len = nums.length;
  if (!len) return -1;
  let [left, right] = [0, len - 1];
  while (left <= right) {
    let mid = left + Math.floor((right - left) / 2);
    let num = nums[mid];
    if (num === target) return mid;
    else if (num > target) right = mid - 1;
    else left = mid + 1;
  }
  return -1;
}
module.exports = {
  search: search,
};
相关文章
|
5月前
|
存储 Java 编译器
【搞定Jvm面试】 面试官:谈谈 JVM 类文件结构的认识
【搞定Jvm面试】 面试官:谈谈 JVM 类文件结构的认识
|
5月前
|
缓存 Java 数据库
Java面试50问,女面试官最喜欢问的居然是它!
Java面试50问,女面试官最喜欢问的居然是它!
|
5月前
|
Java 测试技术 持续交付
Java面试50问,女面试官最喜欢问的居然是它!
Java面试50问,女面试官最喜欢问的居然是它!
|
5月前
|
Java 测试技术 开发者
Java面试50问,女面试官最喜欢问的居然是它!
Java面试50问,女面试官最喜欢问的居然是它!
|
5月前
|
XML JSON JavaScript
Java面试50问,女面试官最喜欢问的居然是它!
Java面试50问,女面试官最喜欢问的居然是它!
|
5月前
|
Java 数据库连接 数据库
Java面试50问,女面试官最喜欢问的居然是它!
Java面试50问,女面试官最喜欢问的居然是它!
|
5月前
|
Java 数据库连接 数据库
Java面试50问,女面试官最喜欢问的居然是它!
Java面试50问,女面试官最喜欢问的居然是它!
|
5月前
|
设计模式 前端开发 Java
Java面试50问,女面试官最喜欢问的居然是它!
Java面试50问,女面试官最喜欢问的居然是它!
|
5月前
|
Java 数据库连接 数据库
Java面试50问,女面试官最喜欢问的居然是它!
Java面试50问,女面试官最喜欢问的居然是它!
|
5月前
|
Java 数据库连接 数据库
Java面试50问,女面试官最喜欢问的居然是它!
Java面试50问,女面试官最喜欢问的居然是它!