定位寻数

一时失言乱红尘 2023-07-24 13:27 2阅读 0赞

本小节需要你利用二分查找算法来编程。

##### 相关知识 #####

二分查找也称折半查找，它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

##### 算法要求 #####

必须采用顺序存储结构。  
必须按关键字大小有序排列。  
编程要求按从小到大的顺序输入n个整数，然后输入另一个整数，判断该整数在前面输入的n个整数中是否存在，是则输出该整数第一次出现的位置（位置从0开始），否则输出-1。  
输入包括3行：

第一行包含一个整数，表示输入的整数个数n，  
第二行包含n个整数，用空格分隔，  
第三行包含一个要寻找的整数。  
效果如下：  
输入：  
6  
0 2 4 6 8 10  
8  
输出：  
4

#include<iostream>
    using namespace std;
    int main()
    { 
     int n,m,count=0;
     bool k;
     cin>>n;
     int a[n];
     for(int i=0;i<n;i++)
     { 
      cin>>a[i];
     }
     cin>>m;
     k=0;
     for(int i=0;i<n;i++)
     { 
      if(a[i]==m)
      { 
       k=1;
       break;
      }
      count++;
     }
     if(k==0)
     { 
      cout<<-1<<endl;
     }
     else if(k==1)
     { 
      cout<<count<<endl;
     }
    }

或

#include<iostream>
    using namespace std;
    int BinarySearch(int array[], int key, int min, int max);
    int main()
    { 
        int data[1000];
        int n,key=0;
        cin >> n;
        for (int i = 0; i < n ;i++)
        { 
         cin >> data[i];
     }
        cin >> key;
        int result = BinarySearch(data, key, 0, n);
        if(result >= 0)
        { 
            cout << result << endl;
        }
        else
        { 
            cout << "-1" << endl;
        }
        return 0;
    }
    int BinarySearch(int array[], int key, int min, int max)
    { 
        while(min <= max)
        { 
         int mid = (min + max) / 2;
         if (array[mid] == key)
         { 
          return mid;
      }
            else if (array[mid] < key)
            { 
             min = mid + 1;
      }
            else 
            { 
             max = mid - 1;
      }
        }
        return -1;
    }