Binary Search

Binary search is an efficient algorithm for finding an item from a sorted list of items. Binary search, also known as the half-interval search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array

Example 1:

Input: arr[]={1,2,3,4,6},target=3
Output: Element is found                                                                                                         

 Example 2:

Input: arr[]={1,2,3,4,6},target=5
Output: Element is not  found                                                                                                         

Approach

Java

public class BinarySearch {
    public static void main(String[] args) {
        int arr[] = { 1, 2, 3, 4, 6 };
        int target = 3;
        if (searchElement(arr, target))
            System.out.println("Element is found");
        else
            System.out.println("Element is not found");
    }

    private static boolean searchElement(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 true;

        }
        return false;
    }
}
// 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,2,3,4,6};
    int target=3;
    int n=sizeof(arr)/sizeof(arr[0]);
    int index=binarySearch(arr,n,target);
    if(index!=-1)
       cout<<"Element is found\n";
    else 
      cout<<"Element is not found\n";
   return 0;
}
//Time Complexity: O(log(n))
//Space Complexity:O(1)