DAY1: Starting Providing Solution of GFG SDE Sheet

Hello Folks!! Welcome to the DAY1 of the 'GFG SDE SHEET Solution'! In this blog post, I will cover all the questions of the GFG SDE SHEET with a effective and with a easy approach including telling you about the concepts related to that topic.

I preferred C++ as my coding language, for placements purpose u can do it with any language. My basic intension is to go through all the concepts and feels confident after doing 100+ questions.

Question Heading: BINARY SEARCH
Ques: Given a sorted array of size N and an integer K, find the position(0-based indexing) at which K is present in the array using binary search.

Ans:

What is binary search?
Binary search is the search technique that works efficiently on sorted lists. Hence, to search an element into some list using the binary search technique, we must ensure that the list is sorted.

Approaches:

1. Illiterate the array till the length of the array which is(n) where u can go for the Linear Search and u have to check the every element of the array with the (k), if it is in the array , then print the index(i) else print -1 symbolize the element is not found in the array.

// User function template for C++
class Solution {
public:
int binarysearch(int arr[], int n, int k) {
for(int i=0;i<n;i++){
if(arr[i]==k){
return i;
}
}
return -1;
}
};

1. Array should be in increasing order, Binary search for finding the element(k) in the array, then define the lower=0 and upper=arr.length()-1, to cover the whole array and then run the loop while the lower is less than upper, find the middle element using mid=(lower+ upper)/2, then check if (arr[mid]k) then make upper=mid-1, if not found then return -1;

class Solution {
public:
int binarysearch(int arr[], int n, int k) {
int lower=0,upper=n-1;
while(lower<=upper){
int mid=(upper+lower)/2;
if(arr[mid]==k){
return mid;
}
else if(arr[mid]>k){
upper=mid-1;
}
else{
lower=mid+1;
}
}
return -1;
}
};

Congratulations you have successfully learned the Binary Search Concept at the completion of the DAY 1!!
Stay tuned for the next blog, Happy Coding!!