数组之二分查找

本文旨在刷力扣的复习巩固

前言

数组：存储在连续内存空间上的相同类型数据的集合。
Tip:
（1）数组下标从0开始
（2）数组在内存空间的地址是连续的

二分法

对应leetcode704题

二分法使用前提：
（1）数组是有序数组（递增或递减）
（2）数组中无重复下标

区间的定义是“不变量”，在二分查找的过程中保持不变量-每次边界的处理都根据区间的定义来操作。

二分法中的区间定义有两种：
[ l e f t , r i g h t ] [left,right] [left,right], [ l e f t , r i g h t ) [left,right) [left,right)

2.1 二分法（一）

针对区间 [ l e f t , r i g h t ] [left,right] [left,right]的情况
1.定义左右边界
2.while循环（left <= right）因为在区间 [ l e f t , r i g h t ] [left,right] [left,right]当left=right时依然有意义，所以≤
3.定义中间值
4.如果nums[middle]大于目标值，更新右边界 r i g h t = m i d d l e − 1 right = middle - 1 right=middle−1 因为如果right=middle，但是目标值并不可能在middle这里，这个边界处理就有问题，所以右边界 r i g h t = m i d d l e − 1 right = middle - 1 right=middle−1
5.同理，如果nums[middle]小于目标值，更新左边界 l e f t = m i d d l e + 1 left = middle + 1 left=middle+1
6.如果nums[middle]等于目标值，那就返回middle（目标值的数组下标）
7.如果没有目标值，return -1

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right)
        {
        	int middle = left + ((right - left) >> 1);
        	if (nums[middle] > target)
        	{
        		right = middle - 1;
       		}
       		else if (nums[middle] < target)
       		{
       			left = middle + 1;
    		}
    		else
    		{
    			return middle;
   			}
        }
        return -1;
    }
};

2.2 二分法（二）

针对区间 [ l e f t , r i g h t ) [left,right) [left,right)的情况
流程和上面差不多，这里主要记录区别

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size();
        while (left < right)
        {
        	int middle = left + ((right - left) >> 1);
        	if (nums[middle] > target)
        	{
        		right = middle;
       		}
       		else if (nums[middle] < target)
       		{
       			left = middle + 1;
    		}
    		else
    		{
    			return middle;
   			}
        }
        return -1;
    }
};

---

##################
不积跬步，无以至千里
##################