TLE in Binary SEARCH

#1

#include
using namespace std;

int binarysearch(int a[],int n,int key)
{
int s=0,e=n-1;
int mid=(s+e)/2;

while(s<=e)
{
	if(a[mid]==key)
	{
		return mid;
	}

	else if(a[mid]>key)
	{
		e=mid-1;
	}

	else if(a[mid]<key)
	{
		s=mid+1;
	}
}
return -1;

}
int main() {
long long int n;
cin>>n;
int key;
int arr[n];

for(int i=0;i<n;i++)
{
cin>>arr[i];
}
cin>>key;
int index=binarysearch(arr,n,key);

cout<<index;

return 0;

}
:bulb: Arrays-Binary Search

Search Content
Search Icon
Course Progress

14%
Exit Class
Course Content
Course Logistics
1 of 1 contents completed
Pointers and Functions (Concepts)
13 of 13 contents completed
Arrays 1.0 (Problem Solving on 1D Arrays)

#2

Hi @arsh_goyal
Hi you are facing TLE because in the while loop you are checking for arr[mid]==key but remember that you are making changes only to s and e and mid remain the same throughout that is why you are never going to enter the if condition. Solution to that is you again assign value to mid in the while loop using
mid=(s+e)/2
because as value of s and e changes so mid value will also change. And also as you have taken e as n-1 so mid should be computed as (s+e)/2 , -1 is not required because you already have taken e as n-1.

Here is your corrected code :

If your doubt is clear then mark it as resolved.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.