0

Could you please help me how to avoid TLE in the below binary search problem :

Question : https://www.spoj.com/problems/BSEARCH1/ My solution works fine but the problem in editor but when submitting it online it shows TLE. Could you please help me out of this problem. My solution: // Program to find an element of a sorted array using binary search. #include<bits/stdc++.h> using namespace std; int binarysearch(int arr[], int n,int x){ int left=0,right=n-1,mid; while(left<=right) { mid=(left+right)/2; if(arr[mid]==x) return mid; else if(x<arr[mid]) right=mid-1; else left=mid+1; if(left>right) return -1; } } int main(){ int n,q,pos; scanf("%d %d",&n,&q); int arr[n]; for(int i=0;i<n;i++){ cin>>arr[i]; } while(q>0){ q--; int x; cin>>x; pos=binarysearch(arr,n,x); cout<<pos<<"\n"; } }

5th Feb 2019, 2:27 PM
Balaji Pathange
Balaji Pathange - avatar
1 Réponse
0
The problem may be that "cout" is kinda slow, compared to printf There's 2 solutions if that's the problem: 1. Try using printf. 2. There's a way to make cin/cout faster. Just in the beginning of main function or in special function type this: ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); And if you use special function don't forget to call it in main This makes cin/cout as fast as scanf/printf And 0 is actually false, it's just faster to write 0 Hope this will help
5th Feb 2019, 2:46 PM
Дмитрий Мазыло
Дмитрий Мазыло - avatar