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

青葱年少

10 月前

🍳作者：🤳

🙊语录：

📓 专栏：牛客刷题–斩获offer

💭

👉🏻开启刷题之旅

Table of Contents

文章目录

- 🧨 前言
- 🎁 二分查找-I
- 🎉 总结

🧨 前言

🚀 是一个集笔面试系统、题库、课程教育、社群交流、招聘内推于一体的招聘类网站，更是一个专注于程序员的学习和成长的平台。

🪓自学是一个程序员必备的能力，而提高自己的编程能力最好方法就是通过刷题。一次偶然的机会让我发现牛客网这个新大陆，开启自己IT之旅。

这里有个大厂的面试真题，知己知彼百战百胜。

更有在线编程调试功能，提高编程效率。👉🏻开始学习

🎁 二分查找-I

描述（题目简单）考点：二分查找

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

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

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

进阶：时间复杂度 O(log n)，空间复杂度 O(1)

解题思路：

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

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

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

题解：

//语言①： 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,
};