Given a sorted array of size N and an integer K, find the position at which K is present in the array using binary search.
Your Task: You dont need to read input or print anything. Complete the function binarysearch() which takes arr[], N and K as input parameters and returns the index of K in the array. If K is not present in the array, return -1.
Expected Time Complexity: O(LogN) Expected Auxiliary Space: O(LogN) if solving recursively and O(1) otherwise.
Constraints:
1 <= N <= 105
1 <= arr[i] <= 106
1 <= K <= 106
Example 1:
Input:
N = 5
arr[]={1 2 3 4 5}
K = 4
Output: 3
Explanation: 4 appears at index 3.
SOLUTIONS:
1.PYTHON-
#User function template for Python
class Solution:
def binarysearch(self, arr, n, k):
start = 0
end = n
if k not in arr:
return -1
while start <= end:
mid = int((start + end)/2)
if arr[mid] == k:
return mid
elif arr[mid] < k:
start = mid +1
elif arr[mid] > k:
end = mid-1
return -1
2.JAVA-
// User function Template for Java
class Solution {
int binarysearch(int arr[], int n, int k) {
int start =0;
int end=arr.length-1;
int mid = (start+end)/2;
while(start<=end){
mid = (start+end)/2;
if(k==arr[mid]) return mid;
if(k>arr[mid]){
start=mid+1;
}
else{
end = mid-1;
}
}
return -1;
}
}
3.JAVASCRIPT-
// } Driver Code Ends
// User function Template for javascript
/**
* @param {number[]} arr
* @param {number} n
* @param {number} k
* @returns {number}
*/
class Solution {
binarysearch(arr, n, k) {
// code here
let ret = -1;
arr.forEach((val)=>{
if(val == k){
ret = arr.indexOf(val);
return ret;
}
})
return ret;
}
}
4.C++ -
// User function template for C++
class Solution {
public:
int binarysearch(int arr[], int n, int k) {
int beg=0,end=n-1;
// int mid=(beg+end)/2;
while(beg<=end)
{
int mid=(beg+end)/2;
if(arr[mid]==k)
{
return mid;
}
else if(arr[mid]<k)
{
beg=mid+1;
// binarysearch(arr,(n-mid-1),k);
}
else{
end=mid-1;
// binarysearch(arr,mid,k);
}
}
return -1;
}
};
Comments