数据结构与算法：二分查找（心得）

前言

前些天我做了一道题目，题目中要求使用二分查找，我便按照我心中的二分查找，信心满满的提交上去了。结果发现无限循环，后面我便去查阅了资料

 二分查找的条件

1. 用于查找的内容需要是有序的
2. 查找的数量只能是一个

 二分查找的二种方法

1.  左闭右闭
2. 左闭右开

二种用法区别就在于 

1. while循环中 left 和 right 的关系，到底是 left <= right 还是 left < right
2. 迭代过程中 middle 和 right 的关系，到底是 right = mid - 1 还是 right = mid

1. 左闭右闭

左闭右闭：每次查找的区间在[left, right]，因为定义 target 在[left, right]区间，所以

1. 循环条件要使用while(left <= right)，因为当 left == right 这种情况发生的时候，得到的结果是有意义的
2. if(arr[mid] > target) ， right 要赋值为 mid - 1， 因为当前的 arr[mid] 一定不是 target ,那么接下来需要查找范围就是[left, mid - 1]

int search(int arr[], int size, int target) //size是数组的大小，target是需要查找的值
{
    int left = 0;
    int right = size - 1;	  // 定义了target在左闭右闭的区间内，[left, right]
    while (left <= right)     //当left == right时，区间[left, right]仍然有效
    {	
        int mid = left + ((right - left) / 2);//等同于 (left + right) / 2，防止溢出
        if (arr[mid] > target) 
        {
            right = mid - 1;	  //target在左区间，所以[left, mid - 1]
        }
        else if (arr[mid] < target) 
        {
            left = mid + 1;	      //target在右区间，所以[mid + 1, right]
        }
        else 
        {	//既不在左边，也不在右边，那就是找到答案了
            return mid;
        }
    }
    //没有找到目标值
    return -1;
}

 2.左闭右开

左闭右开：每次查找的区间在 [left, right),条件控制应该如下：

1. 循环条件使用while (left < right)
2. if (arr[mid] > target)， right = mid，因为当前的 arr[middle] 是大于 target 的，不符合条件,不能取到 mid，并且区间的定义是 [left, right)，刚好区间上的定义就取不到 right, 所以 right 赋值为 mid。

int search(int arr[], int size, int target) //size是数组的大小，target是需要查找的值
{
    int left = 0;
    int right = size;	  
    while (left < right)     
    {	
        int mid = left + ((right - left) / 2);//等同于 (left + right) / 2，防止溢出
        if (arr[mid] > target) 
        {
            right = mid;	  //target在左区间，所以[left, mid)
        }
        else if (arr[mid] < target) 
        {
            left = mid + 1;	      //target在右区间，所以[mid + 1, right)
        }
        else 
        {	//既不在左边，也不在右边，那就是找到答案了
            return mid;
        }
    }
    //没有找到目标值
    return -1;
}

这二种方法必须匹配使用循环条件和后续的区间赋值