Binary Search

Problem

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.

Examples

Example 1:

Input:
N = 5
arr[] = {1 2 3 4 5} 
K = 4
Output: 3
Explanation: 4 appears at index 3.

Example 2:

Input:
N = 5
arr[] = {11 22 33 44 55} 
K = 445
Output: -1
Explanation: 445 is not present.

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 <= 10^5$
• $1 <= arr[i] <= 10^6$
• $1 <= K <= 10^6$

Solution:

Iterative Approach:

Python

def binarysearch(self, arr, n, k):
    low = 0
    high = n-1
    while low<=high:
        mid = low + (high-low)//2
        if arr[mid]==k:
            return mid
        elif arr[mid]<k:
            low = mid+1
        else:
            high = mid-1
    return -1

Java

int binarysearch(int arr[], int n, int k) {
    int high = n-1;
    int low = 0;
    while (low<=high) {
        int mid = low+(high-low)/2;
        if (arr[mid]==k)
            return mid;
        else if (arr[mid]<k)
            low = mid+1;
        else
            high = mid-1;
    }
    return -1;
}

C++

int binarysearch(int arr[], int n, int k) {
    int high = n - 1;
    int low = 0;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == k)
            return mid;
        else if (arr[mid] < k)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1;
}

C

int binarysearch(int arr[], int n, int k) {
    int high = n - 1;
    int low = 0;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == k)
            return mid;
        else if (arr[mid] < k)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1;
}

• Time Complexity: $O(log n)$
• Space Complexity: $O(1)$

Recursive Approach

Python

def binarysearch(arr, low, high, k):
    if low <= high:
        mid = low + (high - low) // 2
        if arr[mid] == k:
            return mid
        elif arr[mid] < k:
            return binarysearch(arr, mid + 1, high, k)
        else:
            return binarysearch(arr, low, mid - 1, k)
    else:
        return -1

Java

int binarysearch(int arr[], int low, int high, int k) {
    if (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == k)
            return mid;
        else if (arr[mid] < k)
            return binarysearch(arr, mid + 1, high, k);
        else
            return binarysearch(arr, low, mid - 1, k);
    }
    return -1;
}

C++

int binarysearch(int arr[], int low, int high, int k) {
    if (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == k)
            return mid;
        else if (arr[mid] < k)
            return binarysearch(arr, mid + 1, high, k);
        else
            return binarysearch(arr, low, mid - 1, k);
    }
    return -1;
}

C

int binarysearch(int arr[], int low, int high, int k) {
    if (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == k)
            return mid;
        else if (arr[mid] < k)
            return binarysearch(arr, mid + 1, high, k);
        else
            return binarysearch(arr, low, mid - 1, k);
    }
    return -1;
}

• Time Complexity: $O(log n)$
• Space Complexity: $O(log n)$