type
Post
status
Published
date
Jun 1, 2024
slug
summary
tags
算法
二分查找
数组
category
算法
icon
password
给定一个
n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。示例 1:
示例 2:
思路:数组为有序数组,同时还强调数组中无重复元素,因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的,这些都是使用二分法的前提条件,当看到题目描述满足如上条件的时候,要想一想是不是可以用二分法了。
边界条件判定:当区间为[x,x]闭区间时,左可以等于右;当为开区间时,左≠右。
为什么用left+((right-left)/2)而不用(right+left)/2?
1.对于16为编译器,int最大为32767
2.对于32位和64位编译器,int最大为2147483647
使用(right+left)/2,当分子的值超过最大值时会造成溢出,left+((right-left)/2)实际上限制了相加的两个数字大小
- Author:guderain
- URL:https://wangguanxi.space/article/6749608d-a64e-4b08-a334-49d9354e2b2e
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
Relate Posts

.webp?table=collection&id=92be88af-5f71-4631-9d3e-ee3bd53dcced&t=92be88af-5f71-4631-9d3e-ee3bd53dcced&width=1080&cache=v2)
