二分查找简括及其个人看法

二分查找

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
总体来说二分查找是建立在按顺序从小到大排好的基础上的（c++上建议用sort）但是具体问题具体讨论；

下面是我按照老师上课讲的略作修改写大二分查找代码

#include <stdio.h>//将代码以函数的形式写在外面很大程度上增加了代码的可读性
int twosearch(int x, int v[], int n){
	int low, high, mid;
	low = 0;
	high = n - 1;
	while ( low <= high ) {
		mid = (low + high) / 2;
		if(x < v[mid]){
			high = mid - 1;
		}
		else if(x > v[mid]){
			low = mid + 1;
		}
		else{ 
			return mid;
		}
	}
	return -1;
}
 
int main(){
	int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
	int ans,n;
scanf("%d",&n);
	ans = twosearch(n, a, 11);
	if(ans==-1)
    printf("failure!\n");
else
	{
	printf("success!\n");
	printf("%d的下标为%d\n",n,ans);
	}
	return 0;
}

##个人看来，二分查找有两个易错点，那就是“越界”和“死循环”。在知乎上看到感觉挺好的就保存下来了

//（1）左闭右开：
int BinarySearch(SeqList* s, DataType x)
{
    int left = 0, right = s->size ;   //
    while (left <right)                     //左闭右开，加上“=”不越界
    {
        int mid = left + (right - left) / 2;
        if (s->array[mid] < x)
        {
            left = mid + 1;             //不加1容易死循环
        }
        else if (s->array[mid]>x)
        {
            right = mid - 1;
        }
        else
        {
            return mid;
        }
    }
}
/*这里int left = 0, right = s->size ;
while (left < right)  这俩句可以看出是左闭右开"[ ）"的情况，如果 if (s->array[mid]>x)满足，那么x在[left,mid）中，right此时应该设置为mid，如果按照上面代码中的right = mid - 1; 就有可能丢失mid对应的那个值，也就是array[mid]=x，这个值被忽略了，就有可能一直找不到x了。*/
//（2）左闭右闭：
 int BinarySearch(SeqList* s, DataType x)
    {
        int left = 0, right = s->size-1 ;   //
        while (left <=right)                     //左闭右闭，加上“=”不越界
        {
            int mid = left + (right - left) / 2;//防溢出
            if (s->array[mid] < x)
            {
                left = mid+1;             //不加1容易死循环
            }
            else if (s->array[mid]>x)
            {
                right = mid-1;
            }
            else
            {
                return mid;
            }
        }
    }
//这个就是对的。
//（3）死循环：
int BinarySearch(SeqList* s, DataType x)
{
    int left = 0, right = s->size-1 ;   //
    while (left <=right)                     //左闭右闭，加上“=”不越界
    {
        int mid = left + (right - left) / 2;//防溢出
        if (s->array[mid] < x)
        {
            left = mid ;             //不加1容易死循环
        }
        else if (s->array[mid]>x)
        {
            right = mid;
        }
        else
        {
            return mid;
        }
    }
}

左闭右闭如果像上面一样满足 if (s->array[mid]>x)，那么x在[left,mid-1]中，right此时应该设置为mid-1，如果这里mid不减1，就有可能在错误的区间死循环，一直找不到不能终止程序。

以下为二分的拓展（个人无聊写的 有的是知乎上看到的）
1.求最小的i，使得a[i] = key，若不存在，则返回-1

int binary_search_1(int a[], int n, int key)
{
    int m, l = 0, r = n - 1;//闭区间[0, n - 1]
    while (l < r)
    {
        m = l + ((r - l) >> 1);//向下取整
        if (a[m] < key) l = m + 1;
        else r = m;
    }
    if (a[r] == key) return r;
    return -1;
}

2.求最大的i，使得a[i] = key，若不存在，则返回-1

int binary_search_2(int a[], int n, int key)
{
    int m, l = 0, r = n - 1;//闭区间[0, n - 1]
    while (l < r)
    {
        m = l + ((r + 1 - l) >> 1);//向上取整
        if (a[m] <= key) l = m;
        else r = m - 1;
    }
    if (a[l] == key) return l;
    return -1;
}

3.求最小的i，使得a[i] > key，若不存在，则返回-1

int binary_search_3(int a[], int n, int key)
{
    int m, l = 0, r = n - 1;//闭区间[0, n - 1]
    while (l < r)
    {
        m = l + ((r - l) >> 1);//向下取整
        if (a[m] <= key) l = m + 1;
        else r = m;
    }
    if (a[r] > key) return r;
    return -1;
}

4.求最大的i，使得a[i] < key，若不存在，则返回-1

int binary_search_4(int a[], int n, int key)
{
    int m, l = 0, r = n - 1;//闭区间[0, n - 1]
    while (l < r)
    {
        m = l + ((r + 1 - l) >> 1);//向上取整
        if (a[m] < key) l = m;
        else r = m - 1;
    }
    if (a[l] < key) return l;
    return -1;
}

实际上，对于3、4，也可以先判断解是否存在，再进行二分查找。显然，上面的代码还不够简洁。下面是我认为最简洁的代码：

1.int ans = std::lower_bound(a, a + n, key) - a;
ans = (ans == n || a[ans] != key) ? -1 : ans;
2.int ans = std::upper_bound(a, a + n, key) - a;
ans = (ans == 0 || a[ans - 1] != key) ? -1 : ans - 1;
3.int ans = std::upper_bound(a, a + n, key) - a;
ans = (ans == n) ? -1 : ans;
4.int ans = std::lower_bound(a, a + n, key) - a;
ans = (ans == 0) ? -1 : ans - 1;