《二分查找算法：在有序数组中搜索目标值》

目录

一、问题分析

二、二分查找算法原理

三、代码实现

---

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target，我们要写一个函数来搜索 nums 中的 target，如果目标值存在就返回它的下标，否则返回 -1。

一、问题分析

既然数组是有序的，那么我们自然而然地会想到一种高效的查找算法 —— 二分查找（Binary Search）。二分查找的基本思想是将查找区间不断缩小一半，直到找到目标元素或者确定目标元素不存在为止。

二、二分查找算法原理

1. 首先，我们确定查找区间的左右边界。初始时，左边界 left 为 0，右边界 right 为数组的长度 n - 1。
2. 然后，在每一轮查找中，我们计算中间元素的下标 mid，计算公式为 mid = left + (right - left) // 2。这里使用 left + (right - left) // 2 而不是简单的 (left + right) // 2 是为了避免在 left 和 right 很大时出现整数溢出的情况。
3. 接下来，我们比较中间元素 nums[mid] 和目标值 target：
   • 如果 nums[mid] == target，那么我们就找到了目标值，直接返回 mid 即可。
   • 如果 nums[mid] < target，这说明目标值在中间元素的右侧，我们就将左边界 left 更新为 mid + 1，继续在右侧区间进行查找。
   • 如果 nums[mid] > target，这说明目标值在中间元素的左侧，我们就将右边界 right 更新为 mid - 1，继续在左侧区间进行查找。
4. 不断重复上述步骤，直到左边界 left 大于右边界 right，这时候就说明目标值不存在于数组中，我们返回 -1。

三、代码实现

class Solution {public int search(int[] nums, int target) {int left = 0;int right = nums.length-1;while(left<=right){int mid = (left+right)/2;if(nums[mid]==target){//相等 找到啦return mid;}else if(nums[mid]<target){left = mid+1;}else{//目标值小right = mid-1;}}//没找到return -1;}
}