Topic: Searching
Questions Attempted: 2
1 | Searching an element in a sorted array |
2 | Search an Element in an array |
Questions Successfully Completed: 2
Searching an element in a sorted array
Time Complexity : O(logn)
Space Complexity : O(1)
Question
Input: N = 5, K = 6 arr[] = {1,2,3,4,6} Output: 1 Explanation: Since 6 is present in the array at index 4 (0-based indexing), the output is 1.
static int searchInSorted(int arr[], int N, int K)
{
int low = 0;
int high = N;
while(low<=high){
int mid = (low+high)/2;
if(arr[mid]==K){
return 1;
}
else if(arr[mid]<K){
low = mid+1;
}
else{
high = mid -1;
}
}
return -1;
}
Searching an element in an array
Time Complexity : O(n)
Space Complexity : O(1)
Question
Input: n = 4 arr[] = {1,2,3,4} x = 3 Output: 2 Explanation: There is one test case with array as {1, 2, 3 4} and element to be searched as 3. Since 3 is present at index 2, the output is 2.
static int search(int arr[], int N, int X)
{
for(int i=0;i<N;i++){
if(arr[i]==X){
return i;
}
}
return -1;
}
Thank you for Reading :)