In this article we will see How to search an Element in a sorted array using Binary Search. If element is not found in the input array the method should return -1.

Input: new int[] { 1, 2, 3, 4, 5, 6 }, 3
Output: 2

Input: new int[] { 1, 2, 3, 4, 5, 6 }, 7
Output: -1

Input: new int[] { 1 }, 1
Output: 0

The idea is to find mid of array, if element is equals to element at mid, return mid else if element is less than mid consider left array to search else consider right array to search.

package com.tb.array;

public class BinarySearchImpl {

 private static int binarySearch(int[] arr, int start, int end, int element) {
  if (start > end)
   return -1;

  int mid = (end + start) / 2;
  if (arr[mid] == element)
   return mid;
  else if (arr[mid] > element)
   return binarySearch(arr, start, mid - 1, element);
  else
   return binarySearch(arr, mid + 1, end, element);

 }

 public static void main(String[] args) {
  System.out.println(binarySearch(new int[] { 1, 2, 3, 4, 5, 6 }, 0, 5, 3));
  System.out.println(binarySearch(new int[] { 1, 2, 3, 4, 5, 6 }, 0, 5, 7));
  System.out.println(binarySearch(new int[] { 1 }, 0, 0, 1));

 }

}

Output: Above code will print something like this on console.

2
-1
0

This program search an element in a sorted array in O(log n) time complexity and O(1) extra space, if you have some better way to solve this logical problem please share your thoughts in comments below.