[已解决]二分查找

hamletroy

求帮助

最佳答案

月排行榜 / 总排行榜

jackz007

2022-11-16 18:47:16

1. #include <stdio.h>
   
2. 
   
3. int find(int d[] , int n , int k)
   
4. {
   
5.         int i , r , left , mid , right                            ;
   
6.         for(r = -1 , left = 0 , right = n - 1 ; left <= right ;) {
   
7.                 mid = left + (right - left) / 2                   ;
   
8.                 if(d[mid] == k) {
   
9.                         r = mid                                   ;
   
10.                         break                                     ;
    
11.                 } else {
    
12.                         if(k > d[mid]) left = mid + 1             ;
    
13.                         else right = mid - 1                      ;
    
14.                 }
    
15.         }
    
16.         return r                                                  ;
    
17. }
    
18. 
    
19. int main(void)
    
20. {
    
21.         int a[100] = {0} , i , k , n , m                          ;
    
22.         scanf("%d" , & n)                                         ;
    
23.         for(i = 0 ; i < n ; i ++) scanf("%d" , & a[i])            ;
    
24.         scanf("%d" , & m)                                         ;
    
25.         if((k = find(a , n , m)) >= 0) printf("%d\n" , k)         ;
    
26.         else printf("null\n")                                     ;
    
27. }

复制代码

        编译运行实况：

1. D:\[00.Exerciese.2022]\C>g++ -o x x.c
   
2. 
   
3. D:\[00.Exerciese.2022]\C>x
   
4. 15
   
5. 1 4 9 13 21 34 55 89 144 233 377 570 671 703 812
   
6. 34
   
7. 5
   
8. 
   
9. D:\[00.Exerciese.2022]\C>

复制代码

跳转到最佳答案楼层

jackz007

1. #include <stdio.h>
   
2. 
   
3. int find(int d[] , int n , int k)
   
4. {
   
5.         int i , r , left , mid , right                            ;
   
6.         for(r = -1 , left = 0 , right = n - 1 ; left <= right ;) {
   
7.                 mid = left + (right - left) / 2                   ;
   
8.                 if(d[mid] == k) {
   
9.                         r = mid                                   ;
   
10.                         break                                     ;
    
11.                 } else {
    
12.                         if(k > d[mid]) left = mid + 1             ;
    
13.                         else right = mid - 1                      ;
    
14.                 }
    
15.         }
    
16.         return r                                                  ;
    
17. }
    
18. 
    
19. int main(void)
    
20. {
    
21.         int a[100] = {0} , i , k , n , m                          ;
    
22.         scanf("%d" , & n)                                         ;
    
23.         for(i = 0 ; i < n ; i ++) scanf("%d" , & a[i])            ;
    
24.         scanf("%d" , & m)                                         ;
    
25.         if((k = find(a , n , m)) >= 0) printf("%d\n" , k)         ;
    
26.         else printf("null\n")                                     ;
    
27. }

复制代码

        编译运行实况：

1. D:\[00.Exerciese.2022]\C>g++ -o x x.c
   
2. 
   
3. D:\[00.Exerciese.2022]\C>x
   
4. 15
   
5. 1 4 9 13 21 34 55 89 144 233 377 570 671 703 812
   
6. 34
   
7. 5
   
8. 
   
9. D:\[00.Exerciese.2022]\C>

复制代码

柿子饼同学

没有重复的吧

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int arr[520];  // 1314
   
5. int n, target;
   
6. int ans;
   
7. 
   
8. int main(){
   
9.     ios::sync_with_stdio(0);
   
10.     cin.tie(0);
    
11. 
    
12.     cin >> n;
    
13.     for(int i = 0; i < n; i++) cin >> arr[i];
    
14.     cin >> target;
    
15. 
    
16.     int l = 0, r = n-1, mid;
    
17. 
    
18.     while(l <= r){
    
19.         mid = (l + r) / 2;
    
20.         if(arr[mid] > target) r = mid - 1;
    
21.         else l = mid + 1, ans = mid;
    
22.     }
    
23. 
    
24.     if(arr[ans] == target) cout << ans ;
    
25.     else cout << "null";
    
26. 
    
27.     return 0;
    
28. }

复制代码