折返查找发（半分查找）

折返查找发（半分查找）

半分查找法是在有序数组中查找效率很高的方法。

半分方法有俩种，各有优缺点。

int _find(int x)
{int l=-1,r=_end;while(r-l>1){int mid = (l+r)/2;if(arr[mid]>=x) r = mid;else l=mid;}return r;
}

此方法是左开右闭，查找的所有相等的会放在右边，

最后返回与查找数相等的元素下标最小的那个。

如果查找的数比数组中所有数都大

会返回 数组最大下标+1;

但是如果比所有数都小，那么会返回最小下标，需要

重新比较arr[0]与x大小。

int _find(int x)
{int l=-1,r=_end;while(r-l>1){int mid = (l+r)/2;if(arr[mid]<=x) l = mid;else r=mid;}return l;
}

这种是左闭右开,所有与查找值相等的都会出现在左边，最后返回下表最大的元素。

如果数比数组中所有数都大，会返回最大下标，需要重新判断arr[n]与x大小。

如果查找数比所有数都小，那么会返回-1。