## 二分查找学习札记

2018年04月24日 ⁄ 综合 ⁄ 共 2989字 ⁄ 字号 评论关闭

# 二分查找算法基本思想

```left = 0, right = n -1
while (left <= right)
mid = (left + right) / 2
case
x[mid] < t:    left = mid + 1;
x[mid] = t:    p = mid; break;
x[mid] > t:    right = mid -1;

return -1;```

## 第一个正确的程序

```int search(int array[], int n, int v)
{
int left, right, middle;

left = 0, right = n - 1;

while (left <= right)
{
middle = (left + right) / 2;
if (array[middle] > v)
{
right = middle;
}
else if (array[middle] < v)
{
left = middle;
}
else
{
return middle;
}
}

return -1;
}```

# 一些问题

## 边界错误造成的问题

right].需要注意的是, 循环体外的初始化条件,与循环体内的迭代步骤, 都必须遵守一致的区间规则,也就是说,如果循环体初始化时,是以左闭右开区间为边界的,那么循环体内部的迭代也应该如此.如果两者不一致,会造成程序的错误.比如下面就是错误的二分查找算法:

```int search_bad(int array[], int n, int v)
{
int left, right, middle;

left = 0, right = n;

while (left < right)
{
middle = (left + right) / 2;
if (array[middle] > v)
{
right = middle - 1;
}
else if (array[middle] < v)
{
left = middle + 1;
}
else
{
return middle;
}
}

return -1;
}```

- 1了,这样,如果恰巧middle-1就是查找的元素,那么就会找不到这个元素.

```int search2(int array[], int n, int v)
{
int left, right, middle;

left = 0, right = n - 1;

while (left <= right)
{
middle = (left + right) / 2;
if (array[middle] > v)
{
right = middle - 1;
}
else if (array[middle] < v)
{
left = middle + 1;
}
else
{
return middle;
}
}

return -1;
}

int search3(int array[], int n, int v)
{
int left, right, middle;

left = 0, right = n;

while (left < right)
{
middle = (left + right) / 2;

if (array[middle] > v)
{
right = middle;
}
else if (array[middle] < v)
{
left = middle + 1;
}
else
{
return middle;
}
}

return -1;
}```

## 死循环

```int search_bad2(int array[], int n, int v)
{
int left, right, middle;

left = 0, right = n - 1;

while (left <= right)
{
middle = (left + right) / 2;
if (array[middle] > v)
{
right = middle;
}
else if (array[middle] < v)
{
left = middle;
}
else
{
return middle;
}
}

return -1;
}```

## 溢出

`middle = (left + right) / 2;`

`middle = left + (right - left) / 2;`

# 更完善的算法

《编程珠玑》中给出了解决这两个问题的算法,结合前面提到溢出问题我对middle的计算也做了修改:

```int search4(int array[], int n, int v)
{
int left, right, middle;

left = -1, right = n;

while (left + 1 != right)
{
middle = left + （right － left) / 2;

if (array[middle] < v)
{
left = middle;
}
else
{
right = middle;
}
}

if (right >= n || array[right] != v)
{
right = -1;
}

return right;
}```

1.<<编程珠玑>>
2.wiki上关于二分查找的说明:http://en.wikipedia.org/wiki/Binary_search