【面试必刷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,
};
相关文章
|
9天前
|
数据采集 算法 网络协议
最新Python 面试常见问题(1),2024年最新面试官必问的10个问题
最新Python 面试常见问题(1),2024年最新面试官必问的10个问题
最新Python 面试常见问题(1),2024年最新面试官必问的10个问题
|
12天前
|
前端开发 算法
【css炫酷动画】让面试官眼前一亮的故障风格文字动画,3年Web前端开发工程师面试经验分享
【css炫酷动画】让面试官眼前一亮的故障风格文字动画,3年Web前端开发工程师面试经验分享
|
12天前
|
设计模式 前端开发 网络协议
Android 开发网易面试凉凉经,面试官:基础不牢,彻底帮你搞懂
Android 开发网易面试凉凉经,面试官:基础不牢,彻底帮你搞懂
|
14天前
|
分布式计算 监控 大数据
《吊打面试官》- 大数据工程师50道中大厂面试真题保姆级详解
《吊打面试官》- 大数据工程师50道中大厂面试真题保姆级详解
29 1
《吊打面试官》- 大数据工程师50道中大厂面试真题保姆级详解
|
14天前
|
监控 安全 Java
【面试题】面试必备我跟面试官聊了一个小时线程池!
【面试题】面试必备我跟面试官聊了一个小时线程池!
|
14天前
|
NoSQL 算法 Java
面试美团被问到了Redis,搞懂这几个问题,让你轻松吊打面试官
每一个程序员都拥有一座大厂梦,很多Java开发者面试之前,可能没有较长的工作时间或者较为丰富的工作经验,所以不知道互联网公司或者一线互联网公司技术面试都会问哪些问题? 再加上可能自己准备也不充分,去面试没几个回合就被面试官几个问题打蒙了,最后以惨败收场。
|
14天前
|
监控 Java 测试技术
面试准备不充分,被Java守护线程干懵了,面试官主打一个东西没用但你得会
面试准备不充分,被Java守护线程干懵了,面试官主打一个东西没用但你得会
31 1
|
14天前
|
人工智能 算法
AI面试官,自动化面试时代来临,我们准备好了吗?
【2月更文挑战第17天】AI面试官,自动化面试时代来临,我们准备好了吗?
65 1
AI面试官,自动化面试时代来临,我们准备好了吗?
|
14天前
|
机器学习/深度学习 算法 搜索推荐
|
14天前
|
程序员
用GPT在技术面试作弊,竟没有一个面试官发现?
用GPT在技术面试作弊,竟没有一个面试官发现?
124 2