/** * 書:《設(shè)計和算法分析》 * 特征:二進制搜索 * 1、建立a[0:n-1]是一排的陣列已經(jīng)好序。請重寫二進制搜索算法，因此，搜索元素時x不用時，該陣列。返回小于x最大的元素 * S檔I而超過x最小的元素位置j。在數(shù)組中的時候。I和j同樣，均為x在數(shù)組中的位置 * 文件:lesson3.cpp * 時間:2014年11月4日19:50:20 * 作者:cutter_point */#include <iostream>using namespace std;//這里a是用來搜索的序列，n是序列里面數(shù)據(jù)的個數(shù),x是要找的數(shù)，i和j是用來找位置的 bool erFen(int *a, int n, int x, int& i, int& j) //i和j是兩個引用 {int left = 0; //查找的起始點int right = n - 1; //查找的終點while (left < right) //僅僅要還有數(shù)據(jù)沒有被遍歷,那就一直循環(huán)一直到找到，或者沒有{int mid = (left + right) / 2; //二分法的精髓，一分為二if (x == a[mid]) //從中間開始比較{i = j = mid; //假設(shè)正好是中間的那個數(shù)的話,把位置賦值給i,jcout << "位置是：" << mid+1<<endl;return true;}//假設(shè)不是中間那個地方的話if (x > a[mid]) //因為是已經(jīng)排好序了{//得到當前小于x的元素的位置j = mid;left = mid + 1; //把后半部分作為新的起點}else{//得到當前大于x的元素位置i = mid;right = mid - 1; //把前半部分作為新的數(shù)列}}//假設(shè)沒有找到//i = right;//j = left;cout << "位置是：" << j+1 << " 和 " << i+1 << "之間" << endl;return false; }int main() {int n, x, i=0, j=0;n = 0;cout << "依次輸入數(shù)列的長度n,要找的整數(shù)x(中間用空格隔開)" << endl;cin >> n >> x;int *a;a = new int[n];cout << "輸入數(shù)組數(shù)據(jù)：" << endl;for (int i = 0; i < n; ++i){cin >> a[i];}erFen(a, n, x, i, j); //i和j有兩個引用getchar();return 0; }

版權(quán)聲明：本文博客原創(chuàng)文章，博客，未經(jīng)同意，不得轉(zhuǎn)載。

轉(zhuǎn)載于:https://www.cnblogs.com/blfshiye/p/4752991.html

總結(jié)

以上是生活随笔為你收集整理的【设计和算法分析】3、二进制搜索的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。