Binary Search (Find index of given target value in array)

Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4                                                                                                        

Approach

Java

public class BinarySearch {
    public static void main(String[] args) {
        int arr[] = { -1, 0, 3, 5, 9, 12 };
        int target = 9;
        int index = search(arr, target);
        System.out.println(index);

    }

    private static int search(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] > target)
                high = mid - 1;
            else if (arr[mid] < target) {
                low = mid + 1;
            } else
                return mid;

        }
        return -1;
    }
}
// Time Complexity : O(log(n))
// Space Complexity: O(1)

C++

#include <bits/stdc++.h>
using namespace std;
//Function to find the element in array
int binarySearch(int arr[], int n, int target)
{
    int low = 0, high = n - 1;
    while (low <= high)
    {
        int mid = low + (high - low) / 2;
        //if target is same as mid element
        if (arr[mid] == target)
            return mid;
        //if target is large then mid
        else if (arr[mid] < target)
            low = mid + 1;
        //if target is small then mid
        else
            high = mid - 1;
    }
    return -1;
}
int main()
{
    int arr[] = {-1, 0, 3, 5, 9, 12};
    int target = 9;
    int n = sizeof(arr) / sizeof(arr[0]);
    int index = binarySearch(arr, n, target);
    cout << index;
    return 0;
}
//Time Complexity: O(log(n))
//Space Complexity:O(1)