DSA Day 6/100

DSA Day 6/100

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 :)