二分查找-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, };