题目描述
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
思路分析
此题即有序列表中查找指定元素，是二分查找典型的应用场景。
二分查找主要总结有以下要点：（从左到右依次递增的数组为例）
- 开始/结束元素定位（初始化时开始元素 left 为列表第一个下标即 0 ，结束元素 right 定位为 length - 1。减一的原因是计算机计数是从 0 开始，长度为 length 的数组最后一个元素下标为 length - 1）
- 中间元素定位（中间元素 mid 计算公式为 left + (right - left)/2 ，采取向下取整的方式，长度为 8 的数组，第一次计 mid 为 0+(7-0)/2 = 3，也就是下标为 3 的元素作为第一次查找的中间元素。向上取整和向下取整不会影响查询结果，两种方式是对称的。向下取整的方式等同于将数组翻转后的向上取整）
- 每次判断后开始/结束元素修改（如果恰巧相等，则可以直接完成查找；如果中间元素小，则待查找对象可能存在右半边，将 left 移动至 mid+1位置；如果中间元素大，则待查找对象可能存在左半边，将 right 移动至 mid-1 位置。此处 mid ±1 可以减少匹配此处，因为 mid 位置已经确定不相等了就不必再纳入查找的列表中。）
- 查找结束条件（查找有两种可能存在/不存在，查找结束条件可以设置为 left <= right。此处等号很关键，如果 [1,2] 中查找2，第一次 left = 0，right = 1，mid = 0 ** 中间值小需要查右边，此时left = 1，right = 1，mid = 1** 匹配成功。等号主要在 length 防止遗漏。 ）
参考代码
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = left + (right - left)/2;
if(nums[mid] == target) return mid;
if(nums[mid] < target) left = mid + 1;
if(nums[mid] > target) right = mid -1;
}
return -1;
}
通过以下网站测试：
力扣测试连接
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
