PTA

二分查找法

题目：用二分法在一个有序数列{1,2,3,4,5,6,7,8,9,10}中查找key值，若找到key则输出其在数组中对应的下标，否则输出not found。

输入格式:

直接输入一个要查找的正整数key。没有其它任何附加字符。

输出格式:

找到则在一行中按照“weizhi:下标”的格式输出其在数组中对应的下标，否则输出not found。

输入样例1:

4

输出样例1:

weizhi:3

输入样例2:

15

输出样例2:

not found

#include <iostream>using namespace std;int BinarySearch(int *p, int n, int x);int main()
{int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};   int x;cin >> x;int m;m = BinarySearch(a, 10, x);if (m >= 0)cout << "weizhi:" << m;elsecout << "not found";
}int BinarySearch(int *p, int n, int x)
{int low, mid, high;  low = 0; high = n - 1;while (low <= high){mid = (low + high) / 2;if (x == p[mid])   return mid;else if (x < p[mid])high = mid - 1;elselow = mid + 1;}return -1;  
}

小结：

二分查找 ——Binary Search

一、含义： 二分查找也称 折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。时间复杂度：O（log2n）

二、代码实现

int BinarySearch(int *p, int n, int x)   // n代表数组元素的个数，  查找的数为X
{int low, mid, high;  // 区间上，下界及中间值 low = 0;  high = n - 1;// 循环判定条件：合理的查找范围while (low <= high){mid = (low + high) / 2;   //  为了防止数值溢出if (x == p[mid])    // *(p + mid) 等价于 p [mid] return mid;else if (x < p[mid])high = mid - 1;elselow = mid + 1;}return -1;   // -1代表没找到 	
}

注：

循环判定条件：low <= high
为了防止数值溢出：mid = (low + high) / 2;
当p[mid]不等于x时，high = mid - 1;或low = mid + 1;

PTA

二分查找法

题目：用二分法在一个有序数列{1,2,3,4,5,6,7,8,9,10}中查找key值，若找到key则输出其在数组中对应的下标，否则输出not found。

输入格式:

直接输入一个要查找的正整数key。没有其它任何附加字符。

输出格式:

找到则在一行中按照“weizhi:下标”的格式输出其在数组中对应的下标，否则输出not found。

输入样例1:

4

输出样例1:

weizhi:3

输入样例2:

15

输出样例2:

not found

#include <iostream>using namespace std;int BinarySearch(int *p, int n, int x);int main()
{int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};   int x;cin >> x;int m;m = BinarySearch(a, 10, x);if (m >= 0)cout << "weizhi:" << m;elsecout << "not found";
}int BinarySearch(int *p, int n, int x)
{int low, mid, high;  low = 0; high = n - 1;while (low <= high){mid = (low + high) / 2;if (x == p[mid])   return mid;else if (x < p[mid])high = mid - 1;elselow = mid + 1;}return -1;  
}

小结：

二分查找 ——Binary Search

一、含义： 二分查找也称 折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。时间复杂度：O（log2n）

二、代码实现

int BinarySearch(int *p, int n, int x)   // n代表数组元素的个数，  查找的数为X
{int low, mid, high;  // 区间上，下界及中间值 low = 0;  high = n - 1;// 循环判定条件：合理的查找范围while (low <= high){mid = (low + high) / 2;   //  为了防止数值溢出if (x == p[mid])    // *(p + mid) 等价于 p [mid] return mid;else if (x < p[mid])high = mid - 1;elselow = mid + 1;}return -1;   // -1代表没找到 	
}

注：

循环判定条件：low <= high
为了防止数值溢出：mid = (low + high) / 2;
当p[mid]不等于x时，high = mid - 1;或low = mid + 1;