數組查找演算法
1. 查找演算法：採用二分法在有序數組 中查找一數，指出數的位置和查找次數。
#include<iostream>
usingnamespacestd;
voidBinarySearch(int*list,intlen,intkey,int*index_t){
//最低邊界
intlow=0;
//最高邊界
inthigh=len-1;
while(low<=high){
index_t[0]++;
//取中間值
intmiddle=(low+high)/2;
if(list[middle]==key){
index_t[1]=middle;
return;
}
elseif(list[middle]>key){
//下降一半
high=middle-1;
}
else{
//上升一半
low=middle+1;
}
}
//沒找到
index_t[1]=-1;
}
intmain(){
constintN=10;
intlist[N]={3,9,11,12,21,23,56,61,89,98};
intindex_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;
}
2. 如何用二分查找法查找一個數組中的元素
二分查找又叫折半查找，但是有一個前提條件，就是你要查找的數據必須是按順序儲存，以關鍵字大小來排列的。
例如
如果是整形數組，存放0~9這10個數，數組必須按0到9（升序）或者9到0（降序）挨個儲存。
如果你數組的元素之字元串，字元串的首字母就得按a~z或者z~a挨個儲存，當最高位相同時比較次高位。
當你保證數組有序後，就可以開始執行二分查找了。
舉個例子
1,3,6,8,9,10,11,15
如果你要查找的數字是10，查找過程如下
由於一共有7個元素，比較最中間的元素，即第四個，10>9，由於是升序排列，選擇9的右邊三個數進行比較,，這就將比較次數縮短了一半。在右半部分再去中間元素，即11,10<11，選取11左邊部分進行比較，即和10進行比較，得到要找的元素。
當然也存在找不到的情況，比如找12，先與9比，范圍縮小至右半部分，跟11比，在此基礎上再縮小至現有右半部分，只剩一個15，不相等， 即沒找到想要的元素。
這就是一個遞歸縮小范圍的過程
3. 利用C語言定義有序數組，實現二分查找演算法
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void xuanzhe(int a[], int n)
{
int i, j, min, t;
for (i=0; i<n-1; i++) /*要選擇的次數：0~n-2共n-1次*/
{
min = i; /*假設當前下標為i的數最小，比較後再調整*/
for (j=i+1; j<n; j++)/*循環找出最小的數的下標是哪個*/
{
if (a[j] < a[min])
{
min = j; /*如果後面的數比前面的小，則記下它的下標*/
}
}
if (min != i) /*如果min在循環中改變了，就需要交換數據*/
{
t = a[i];
a[i] = a[min];
a[min] = t;
}
}
}
int main(){
int i,n,x;
int mid,left=0,right=999;
int find1=0,find2=0;
double y;
int a[1000];
for(i=0;i<1000;++i){
a[i]=rand();
}
xuanzhe(a,1000);
scanf("%d",&x);
printf("順序查找:\n");
for(i=0;i<1000;++i){
while(x==a[i]){
printf("找到X=%d,a[%d]\n",x,i);
find1=1;
break;
}
}
if(find1==0){
printf("沒有你要找的數\n");
}
printf("%fs\n",clock()/CLOCKS_PER_SEC);
y=clock();
printf("二分查找:\n");
while(!find2&&left<right)
{
mid=(left+right)/2;
if(x==a[mid])
find2=1;
else if(x<a[mid])
right=mid-1;
else left=mid+1;
}
if(find2==1)
printf("找到x=%d ,a[%d]\n",x,mid);
else
printf("沒有你要找的數\n");
printf("%fs\n",(clock()-y)/CLOCKS_PER_SEC);
}
4. 如何實現無序數組的快速查找
如果只是查找單個數字沒有優化演算法，只能是遍歷所有數字，與指定數字比較，相等則退出，復雜度O（n）;
如果要查找k個指定數字則可以首先將k個數字排序去重，然後採用不同演算法：
1）遍歷所有無序數字，對每個數字用二分查找法到k個數字中搜索是否存在，如存在則表示無序數字中有該數字，否則則沒有，復雜度O(nlogk)。
2）用第k/2個指定數字將原無序數字拆分成兩半----類似與快排的演算法，這樣就知道第k/2個指定數字是否存在了，然後分別用第k/4和3k/4個指定數字拆分第一次拆分出來的兩半無序數組，然後依次進行， 復雜度也為O(nlogk)。
PXE BIS Policy/PXE BIS Default Policy
5. 思考:在含有n個元素的一維數組中順序查找一個。值k的數組元素的演算法: 」考慮此演算法的時間復雜度。
這個搜索演算法的代碼寫錯了。圓括弧的參數表中，第一個參數應該是一個指針參數int *a。還有， 循環部分應該是for(i=0;i<n;i++)，整體應該是：
int search(int *a int n, int k)
{
for(i=0; i<n; i++ )
if(a[i]==k) return i;
return -1;
}
整個查找演算法的時間復雜度是O(n)。
6. 一個無序的數組，有什麼高效的查找演算法
無序的序列，如果只進行極少量的查找，最快也是最簡單的演算法是從順序地掃描查找；
如果是大量地查找，先用快排排序，再用二分查找 ！
7. 數組的冒泡排序和分塊查找法
#include<iostream.h>
const int N=12,M=3;
void numbers (int a[]) //輸入數組元素
{
cout<<"請輸入"<<N<<"個元素"<<endl;
for(int i=0;i<N;i++)
cin>>a;
}
void sort(int a[],int n) //冒泡法排序
{
int t;
for(int i=0;i<n-1;i++)
for(int j=0;j<n-1-i;j++)
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
void search(int a[]) //分塊查找法
{
int x,j,i;
cout<<"請輸入要查找的元素"<<endl;
cin>>x;
int b[N][2];
for(j=0,i=3;j<3,i<12;j++,i+=4)
b[j][0]=a;
for(j=0,i=0;j<3,i<12;j++,i+=4)
b[j][1]=i;
for(j=0;j<3;j++)
{
if(x<=b[j][0])
break;
}
if(x>a[N-1])
{
cout<<x<<" "<<"不在您要查找的數組中"<<endl;
return;
}
{
int top=b[j][1],bottom=b[j][1]+N/M-1,middle=(top+bottom)/2; //折半查找法
while(top<=bottom)
{
if(x==a[middle])
break;
else if(x>a[middle])
top=middle+1;
else
bottom=middle-1;
middle=(top+bottom)/2;
}
if(x==a[middle])
{
cout<<x<<" "<<"在您要查找的數組中"<<endl;
}
else
{
cout<<x<<" "<<"不在您要查找的數組中"<<endl;
}
}
}
8. 用遞歸方法寫出有序數組的二分查找演算法
什麼是二分查找？
二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須採用順序存儲結構，而且表中元素按關鍵字有序排列。
二分查找優缺點
優點是比較次數少，查找速度快，平均性能好；
其缺點是要求待查表為有序表，且插入刪除困難。
因此，折半查找方法適用於不經常變動而查找頻繁的有序列表。
使用條件：查找序列是順序結構，有序。
過程
首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、後兩個子表，如果中間位置記錄的關鍵字大於查找關鍵字，則進一步查找前一子表，否則進一步查找後一子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。
利用循環的方式實現二分法查找
public class BinarySearch {
public static void main(String[] args) {
// 生成一個隨機數組 int[] array = suiji();
// 對隨機數組排序 Arrays.sort(array);
System.out.println("產生的隨機數組為： " + Arrays.toString(array));
System.out.println("要進行查找的值： ");
Scanner input = new Scanner(System.in);
// 進行查找的目標值 int aim = input.nextInt();
// 使用二分法查找 int index = binarySearch(array, aim);
System.out.println("查找的值的索引位置： " + index);
}
/** * 生成一個隨機數組 *
* @return 返回值，返回一個隨機數組 */
private static int[] suiji() {
// random.nextInt(n)+m 返回m到m+n-1之間的隨機數 int n = new Random().nextInt(6) + 5;
int[] array = new int[n];
// 循環遍歷為數組賦值 for (int i = 0; i < array.length; i++) {
array[i] = new Random().nextInt(100);
}
return array;
}
/** * 二分法查找 ---循環的方式實現 *
* @param array 要查找的數組 * @param aim 要查找的值 * @return 返回值，成功返回索引，失敗返回-1 */
private static int binarySearch(int[] array, int aim) {
// 數組最小索引值 int left = 0;
// 數組最大索引值 int right = array.length - 1;
int mid;
while (left <= right) {
mid = (left + right) / 2;
// 若查找數值比中間值小，則以整個查找范圍的前半部分作為新的查找范圍 if (aim < array[mid]) {
right = mid - 1;
// 若查找數值比中間值大，則以整個查找范圍的後半部分作為新的查找范圍 } else if (aim > array[mid]) {
left = mid + 1;
// 若查找數據與中間元素值正好相等，則放回中間元素值的索引 } else {
return mid;
}
}
return -1;
}}
運行結果演示：
總結：
遞歸相較於循環，代碼比較簡潔，但是時間和空間消耗比較大，效率低。在實際的學習與工作中，根據情況選擇使用。通常我們如果使用循環實現代碼只要不是太繁瑣都選擇循環的方式實現~
9. 為什麼要用到數組及遍歷數組和數組里數據的查找方法
查找的意義是在一堆數據中，使用方法找到你想要找的數據。
一般為分：順序和折半（又叫二分）查找兩種方法。
存放在數組中的數據就可以看成一堆數據，在有限數組內存放一些數據，通過使用查找方法進行查找想要找的數。
順序方法：這種查找方法不需要數組排序，數據可以是無序的。從數組開頭向後一個一個與被查找數進行比較，如果找到就做相應的操作（如輸出這個數的下標或位置）等。
折半查找法：（二分查找）
前提需要把數組里的數據進行排序（升序或降序）。思路是（假設數組已按升序排序）每次只比較中間的數據（一段距離內），第一次先和中間的數組（下標是這個數組中在中間的）比較，如果相同，則說明被找數已找到。否則就要判斷是在大於還是小於：如果是大於，那麼就將在中間+1至最後一個數之間的中間數再進行比較。否則就將在第一個至中間-1的數進行比較；再次重復比較，直到找到數為止。
10. 一個無序的數組，有什麼高效率的查找演算法
無序數組只有依次查找，如果需要查找的次數很多，可以先排序，如果需要查找的次數很多很多，而且是按固定的條件進行查詢，那可以考慮建立HASH映射。