二分查找

二分查找的边界问题:

[ left, right ) 左闭右开的情况 1.注意起始的右指针的位置, 因为右指针不包括, 所以是数组长度 2.指针的移动, 虽然不会影响结果, 但是有重复的区间, 所以还是尽量避开重复区间

int  Search_Bin(int arr[], int length,int target){
    int L=0;
    int R=length;
   
    while(L<R){
        int mid = (L+R)/2;                      // 获取中间元素的索引
        if(target>arr[mid]){                    // 如果target大于mid
           l=mid+1;                             // 将左指针右移动到mid+1的位置, 因为刚才左区已经查找过了, 所以要mid+1
        }
        else if(target<arr[mid]){               // 如果target小于mid
           r=mid;                               // 将右指针左移到mid的位置, 因为右边是一个开区间,不包含,所以直接是mid的位置.
        }
        else{
            return mid;                         // mid的数据为targe直接返回当前mid.
        }
    }
    
    return 0;
}

[ left, right ] 左闭右闭的情况 1.注意起始的右指针的位置, 因为右指针的位置也包括在内, 所以是数组长度-1 2.注意左右指针移动区间

int  Search_Bin(int arr[], int length,int target){
    int L=0;
    int R=length-1;
   
    while(L<=R){
        int mid = (L+R)/2;                      
        if(target>arr[mid]){                    
           l=mid+1;                             // 将左指针右移动到mid+1的位置, 因为刚才左区已经查找过了, 所以要mid+1
        }
        else if(target<arr[mid]){               
           r=mid-1;                             // 因为右指针的位置也包含了, 所以需要将右指针移动到mid-1
        }
        else{
            return mid;                         
        }
    }
    
    return 0;
}