#C++1711—— 数据结构-有序表的折半查找

***********************************************************************

①假如要查找数(temp)的位置为5;//为什么left=mid+1

防止left=4,right=5,mid=(right+left)/2=4; //满足num[mid]<temp

重复执行left=mid会陷入死循环,故left=mid+1；

②倘若要查找数(temp)的位置为4://为什么用right输出,当然left也可以

当left=3,right=5,mid=(right+left)/2=4;//满足num[mid]>=temp,执行right=4，同理mid=(4+3)/2==3;

最后num[mid]<temp,左端点踩过来(left=mid+1)，正好相遇；

由此可得right总是踩在正确的结果上

③条件优化

mid=left+((right-left)>>1)//与mid=(right+left)/2同效，但可以防止数值过大,且速度更快

参考代码:

#include <iostream>
using namespace std;
int main()
{
    int n,num[100000],temp,m,right,left,mid;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>num[i];
    }
    while(m--)
    {
        cin>>temp;
        right=n;
        left=0;
        while(left<right)
        {
            mid=left+((right-left)>>1);//二进制右移1位
            if(temp>num[mid])
                left=mid+1;
            else
                right=mid;
        }
      	if(num[right]==temp)//右边始终踩在正确的位置 
      		cout<<right<<" ";
      	else
      		cout<<-1<<" ";
    }
    return 0;
}