一、线性查找

从列表第一个元素开始，直到找到元素或者查找到列表最后一个元素为止。

时间复杂度：O(N)

#include<iostream>
using namespace std;
int linear_search(int arr[], int num) {
	for(int i = 0; i < n; i++) {
    	if(a[i] == num) {
          return i;
        }
    }
  	return -1;
}

int main() {
	int n;
	while(cin >> n) {
    	int a[n];
      	for(int i = 0; i < n; i++) {
      		cin >> a[i];
        }
      	int num;
      	cin >> num;
    	cout << linear_search(a,num) << endl;
    }
  	return 0;
}

二、二分查找

从有序列表的初始候选区开始，通过对待查找的值与候选区中间值的比较，可以使候选区折半。

时间复杂度：O(logN)

二分查找需要有序列表

#include<iostream>
using namespace std;
int binary_search(int a[], int size, int num) {
  	int left = 0,right = size - 1;
	while(left <= right) {
      	int mid = (left + right)/2;
    	if(a[mid] == num) {
          return mid;
        } else if (a[mid] > num) {
          right = mid - 1;
        } else {
          left = mid + 1;
        }
    }
  	return -1;
}

int main() {
	int n;
	while(cin >> n) {
    	int a[n];
      	for(int i = 0; i < n; i++) {
      		cin >> a[i];
        }
      	int num;
      	cin >> num;
    	cout << binary_search(a,num) << endl;
    }
  	return 0;
}