Gfg Searching A Number
Problem Statement
- Given an array Arr of N elements and a integer K. Your task is to return the position of first occurence of K in the given array.
- Array index starts with 1.
Example
Input:
N = 5, K = 16
Arr[] = {9, 7, 2, 16, 4}
Output: 4
Explanation: K = 16 is found in the
given array at position 4.
Solution Approaches
O(N) - Classic Linear Search
- Implementation of Linear Search Algorithm
- Iterate through array, check for each index if current value is equal to k.
- If found return the index+1 as indexing starts with 1
- If not found return -1 as asked.
int search(int arr[], int n, int k) {
// code here
for(int i=0;i<=n;i++){
if(arr[i]==k){
return i+1;
}
}
return -1;
}
O(LogN) - Classic Binary Search
- Implementation of Binary Search Algorithm
int findnum(int arr[], int low, int high, int x) {
if (high >= low) {
int mid = (low + high) / 2;
if (arr[mid] == x) {
return mid;
}
else if (arr[mid] > x) {
return findnum(arr, low, mid - 1, x);
}
else if (arr[mid] < x) {
return findnum(arr, mid + 1, high, x);
}
}
return -1;
}
Return to DSA
Notes mentioning this note
There are no notes linking to this note.