顺序表应用6：有序顺序表查询

顺序表应用6：有序顺序表查询

Time Limit: 1000 ms Memory Limit: 4096 KiB

Submit Statistic

Problem Description

顺序表内按照由小到大的次序存放着n个互不相同的整数，任意输入一个整数，判断该整数在顺序表中是否存在。如果在顺序表中存在该整数，输出其在表中的序号；否则输出“No Found!"。

Input

 第一行输入整数n (1 <= n <= 100000)，表示顺序表的元素个数； 第二行依次输入n个各不相同的有序非负整数，代表表里的元素； 第三行输入整数t (1 <= t <= 100000)，代表要查询的次数； 第四行依次输入t个非负整数，代表每次要查询的数值。

保证所有输入的数都在 int 范围内。

Output

 输出t行，代表t次查询的结果，如果找到在本行输出该元素在表中的位置，否则本行输出No Found!

Sample Input

10 1 22 33 55 63 70 74 79 80 87 4 55 10 2 87

Sample Output

4 No Found! No Found! 10

Hint

Source

 

顺序表应用6：有序顺序表查询

Time Limit: 1000 ms Memory Limit: 4096 KiB

Submit Statistic

Problem Description

顺序表内按照由小到大的次序存放着n个互不相同的整数，任意输入一个整数，判断该整数在顺序表中是否存在。如果在顺序表中存在该整数，输出其在表中的序号；否则输出“No Found!"。

Input

 第一行输入整数n (1 <= n <= 100000)，表示顺序表的元素个数； 第二行依次输入n个各不相同的有序非负整数，代表表里的元素； 第三行输入整数t (1 <= t <= 100000)，代表要查询的次数； 第四行依次输入t个非负整数，代表每次要查询的数值。

保证所有输入的数都在 int 范围内。

Output

 输出t行，代表t次查询的结果，如果找到在本行输出该元素在表中的位置，否则本行输出No Found!

Sample Input

10 1 22 33 55 63 70 74 79 80 87 4 55 10 2 87

Sample Output

4 No Found! No Found! 10

Hint

Source

这个题目看着很简单，用一个结构体什么的就能AC但实际上单纯的用for循环进行查找的话会TLE，虽然最大数据量才是10w但是查找的次数较多，稍微查找次数多一些的话就很容易TLE，所以查找的方式需要进行优化，我们可以采取二分查找的方式进行查找，大大节省时间。这个题其实也就是在让我们重新温习一下二分查找的方法，如果有学C++的朋友并且了解STL函数库的可以直接调用binaryserch函数。

AC代码：

#include<bits/stdc++.h> using namespace std; int a[1000009]; int n; void find(int x) { int l=0,r=n-1,m; while(l<=r) { m=(l+r)/2; if(x>a[m]) { l=m+1; } else if(x<a[m]) { r=m-1; } else { printf("%d\n",m+1); return ; } } printf("No Found!\n"); return ; } int main() { int m,i,x; scanf("%d",&n); for(i=0;i<=n-1;i++) { scanf("%d",&a[i]); } scanf("%d",&m); for(i=0;i<=m-1;i++) { scanf("%d",&x); find(x); } return 0; }

题目其实就到这了，但是我想在这里扩充一下二分查找。

我在上面的代码上写的二分查找函数是最基本的函数，但是这个二分查找的代码还可以进行优化一下。

int searchInsert(vector<int>& nums, int target) { int i = 0; int j = nums.size() - 1; while (i < j) { int mid = i + (j - i) / 2; if (nums[mid] > target) j = mid - 1; else if (nums[mid] == target) //即继续二分查找查找相等元素的左边界即可 j = mid; else i = mid + 1; } if (nums[i] == target) return i; else return -1; }

这个有一个简化的写法，减少比较次数【注意以下写法只适合返回最开始出现的位置，如果题目改成出现的最后的一个位置，则还是得用上面的方法】

int binarySearch(vector<int> &array, int target) { // write your code here int i = 0; int j = array.size() - 1; while (i < j) { int mid = i + (j - i) / 2; if (array[mid] >= target) j = mid ; else i = mid + 1; } if (array[i] == target) return i; else return -1; }