# 二分查找算法基本思想

```1 left = 0, right = n -1
2 while (left <= right)
3     mid = (left + right) / 2
4     case
5         x[mid] < t:    left = mid + 1;
6         x[mid] = t:    p = mid; break;
7         x[mid] > t:    right = mid -1;
8
9 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;
}```

（下面这两个算法是正确的）

``` 1 int search_bad2(int array[], int n, int v)
2 {
3     int left, right, middle;
4
5     left = 0, right = n - 1;
6
7     while (left <= right)
8     {
9         middle = (left + right) / 2;
10         if (array[middle] > v)
11         {
12             right = middle;
13         }
14         else if (array[middle] < v)
15         {
16             left = middle;
17         }
18         else
19         {
20             return middle;
21         }
22     }
23
24     return -1;
25 }```

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

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

``` 1 int search4(int array[], int n, int v)
2 {
3     int left, right, middle;
4
5     left = -1, right = n;
6
7     while (left + 1 != right)//这个循环维持的条件是left<right && array[left]<v<=array[right],所以到最后的时候，
8     {//如果可以找到目标，则只剩下两个数，并且满足 array[left]<v<=array[right],是要查找的数是right
9         middle = left + （right － left) / 2;
10
11         if (array[middle] < v)//必须保证array[left]<v<=array[right]，所以left = middle;
12         {//如果left =middle+1,则有可能出现 array[left]<=v的情况
13             left = middle;
14         }
15         else
16         {
17             right = middle;
18         }
19     }
20
21     if (right >= n || array[right] != v)
22     {
23         right = -1;
24     }
25
26     return right;
27 }```

``` 1 int Bi_Search(int a[],int n,int b)//
2 {//返回等于b的第一个
3     if(n==0)
4         return -1;
5     int low = 0;
6     int high = n-1;
7     int last = -1;//用last记录上一次满足条件的下标
8     while (low<=high)
9     {
10         int mid = low +(high-low)/2;
11         if (a[mid]==b)
12         {
13             last = mid;
14             high = mid -1;
15         }
16         else if(a[mid]>b)
17             high = mid -1;
18         else
19             low = mid +1;
20     }
21
22     return last;
23
24 }
25 int Bi_Search1(int a[],int n,int b)//大于b的第一个数
26 {
27     if(n<=0)
28         return -1;
29     int last = -1;
30     int low = 0;
31     int high = n-1;
32     while (low<=high)
33     {
34         int mid = low +(high - low)/2;
35         if(a[mid]>b)
36         {
37             last = mid;
38             high = mid -1;
39         }
40         else if (a[mid]<=b)
41         {
42             low =mid +1;
43         }
44     }
45
46     return last;
47 }
48 int Bi_Search(int a[],int n,int b)//
49 {//返回等于b的第一个
50     if(n==0)
51         return -1;
52     int low = 0;
53     int high = n-1;
54     int last = -1;//用last记录上一次满足条件的下标
55     while (low<=high)
56     {
57         int mid = low +(high-low)/2;
58         if (a[mid]==b)
59         {
60             last = mid;
61             high = mid -1;
62         }
63         else if(a[mid]>b)
64             high = mid -1;
65         else
66             low = mid +1;
67     }
68
69     return last;
70
71 }
72 int Bi_Search1(int a[],int n,int b)//大于b的第一个数
73 {
74     if(n<=0)
75         return -1;
76     int last = -1;
77     int low = 0;
78     int high = n-1;
79     while (low<=high)
80     {
81         int mid = low +(high - low)/2;
82         if(a[mid]>b)
83         {
84             last = mid;
85             high = mid -1;
86         }
87         else if (a[mid]<=b)
88         {
89             low =mid +1;
90         }
91     }
92
93     return last;
94 }View Code ```

0 条评论

• ### poj----2155 Matrix(二维树状数组第二类)

Matrix Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 16950 ...

• ### 简单的验证码识别（opecv）

opencv版本： 3.0.0            处理验证码： 纯数字验证码 （颜色不同，有噪音，和带有较多的划痕）             ...

• ### HDUOJ---Can you solve this equation?

Can you solve this equation? Time Limit: 2000/1000 MS (Java/Others)    Memory Li...

• ### 归并排序模板

归并排序主要的思想是分治和合并，合并我觉得挺好理解的，分治是用递归实现的感觉不太好理解，我就贴一个模板，拿着就能用了。要是像仔细学习了解归并排序的...

• ### 你真的会写二分查找吗？

二分查找是一个基础的算法，也是面试中常考的一个知识点。二分查找就是将查找的键和子数组的中间键作比较，如果被查找的键小于中间键，就在左子数组继续查找；如果大于中间...

• ### RNG输了，但我们不能输

RNG输了，输在了轻敌，没有把G2当人看，随随便便bp,就是告诉你，我4保1奥巴马我也可以赢，结果啪啪啪打脸。

• ### 你真的会写二分检索吗？

前几天在论坛上看到有统计说有80%的程序员不能够写对简单的二分法。二分法不是很简单的吗？这难道不是耸人听闻？

• ### 力扣LeetCode，区域和检索 - 数组不可变

1、给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。

• ### 精典算法之二分查找法

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列...