Question

查找算法：采用二分法在有序数组 中查找一数，指出数的位置和查找次数。

查找算法：采用二分法在有序数组 int a[N]={3,9,11,12,21,23,56,61,89,98};中查找一数，指出数的位置和查找次数。

Answer 1

#include <iostream>
using namespace std;

void BinarySearch(int* list, int len, int key, int* index_t) {
	//最低边界 
	int low = 0; 
	//最高边界 
	int high = len - 1; 
	while (low <= high) {
		index_t[0]++;
		//取中间值
		int middle = (low + high) / 2;
		if (list[middle] == key) {
			index_t[1] = middle;
			return;
		} 
		else if (list[middle] > key) {
			//下降一半
			high = middle - 1; 
		}
		else {
			//上升一半
			low = middle + 1; 
		}
	} 
	//没找到 
	index_t[1] = -1;
} 

int main() {
	const int N = 10;
	int list[N]= {3, 9, 11, 12, 21, 23, 56, 61, 89, 98};
	int index_t[2] = {0};
	BinarySearch(list, N, 12, index_t);
	
	cout << "查找次数为:" << index_t[0] << endl; 
	if (index_t[1] != -1)
		cout << "已经找到12,索引位置为:" << index_t[1] << endl; 
	else
		cout << "没找到!" << endl;
}