数组_二分查找

一、leetcode-572

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

样例输入：nums = [-1,0,3,5,9,12], target = 9

样例输出： 4

解释: 9 出现在 nums 中并且下标为 4

二、题解

1.代码

class Solution {
public:int search(vector<int>& nums, int target) {for(int i=0,j=nums.size()-1,k;i<=j;){k=(i+j)/2;if(target==nums[k]){return k;}else if(target>nums[k]){i=k+1;}else{j=k-1;}}return -1;}
};

2.思考

对区间的定义想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。
也就是[left, right] （这个很重要非常重要）

1. while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
2. if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1