Binary Search(Java Implementation)

Leave a Comment / Data Structure / By

Binary search works on sorted arrays. Binary search begins by comparing the middle element of the array with the target value. If the target value matches the middle element, its position in the array is returned. If the target value is less than the middle element, the search continues in the lower half of the array. If the target value is greater than the middle element, the search continues in the upper half of the array. By doing this, the algorithm eliminates the half in which the target value cannot lie in each iteration.

Algorithm:

  • step 1 : Compare x(item To Search) with the middle element.
  • step 2 :  If x matches with middle element, return the mid index.
  • step 3 : Else If x is greater than the mid element, then x can only lie in right half subarray after the mid element. So we recur for right half.
  • step 4 : Else (x is smaller) recur for the left half.

Iterative implementation of Binary Search

public class Search {

//return index of item if it is present in arr[]
//else return -1
public int binarySearch(int arr[], int u,int l, int item) 
 {
  while (l <= u) 
   { 
    int mid = (l + u) / 2;
    //check if item is present at middle
    if (arr[mid] == item) 
    return mid; 
    //if item is smaller ignore right half
    else if (arr[mid] > item)
    u = mid - 1;
    else
    //if item is greater ignore left half
    l = mid + 1;
   }
    //return -1 if element is not found
    return (-1);
 }

public static void main(String[] strr) 
{
//l for lower  
//u for upper 
int u, l, itemToSearch;
int arr[] = {1, 2, 10, 13, 17, 29, 33, 42, 49, 98, 100};
u = arr.length - 1;
l = 0;
itemToSearch = 10;
int index = new Search().binarySearch(arr,u,l,itemToSearch);
if (index==-1)
System.out.println("item not exist");
else
System.out.println("Item"+" " +itemToSearch+" " + "found at index :" + index + " and " +"position :" + (index+1));
}
}  

Output:

Item 10 is found at index :2 and position :3

 Recursive implementation of Binary Search

public class Search {
 
public int binarySearch(int arr[], int l,int u, int item)   
 { 
   if (u>=l)
  { 
    int mid = l + (u - l)/2; 
    if (arr[mid] == item){ 
    return mid; 
    } 
    if (arr[mid] > item){ 
    //search in left subarray
    return binarySearch(arr, l, mid-1, item); 
    }
    else{ 
    //search in right subarray 
    return binarySearch(arr, mid+1, u, item);
    } 
  } 
   return -1; 
 }
 
public static void main(String args[]){ 
//l for lower  
//u for upper 
int u, l, itemToSearch;
int arr[] = {1, 2, 10, 13, 17, 29, 33, 42, 49, 98, 100};
u = arr.length - 1;
l = 0;
itemToSearch = 10;
int index = new Search().binarySearch(arr, l, u, itemToSearch); 
if (index==-1)
System.out.println("item not exist");
else
System.out.println("Item"+" " +itemToSearch+" " + "found at index :" + index + " and " +"position :" + (index+1));
}
}

 

Output:

Item 10 is found at index :2 and position :3

Time complexity

As we dispose off one part of the search case during every step of binary search, and perform the search operation on the other half, this results in a worst case time complexity of O(Log n) ,where n is the no of elements in the array.

Leave a Reply