Binary search is a searching technique that is based upon the Divide-and-Conquer Rule.
In this searching technique, a sorted array is divided into two equal halves and then the same technique is applied onto the two halves searching for the element by comparing the high and the low.
Time Complexity (Best)
Ω(1)
Time Complexity (Avg)
Θ(log n)
Time Complexity (Worst)
O(log n)
Space Complexity
O(1)
Working of binary search in JAVA
For Binary Search to be performed on any array, the array must be already sorted in any format, that is, either ascending or descending.
Find the middle index of the array/list.
If the middle element is equal to the search element, Stop Searching.
If the element that is to be searched is less then the middle element then consider the first half as a separate list.
Else-If the element that is to be searched is larger then the middle element then consider the second half as a separate list.
Repeat Step 2-3-4-5 Until desired result is found.
// Binary Search implimentation in Java (Recursive)
// Time Complexity : O(N)
// Space Complexity : O(1)
// Auxiliary Space Complexity : O(N) due to function call stack
public class Main{
public static int binarySearch(int array[], int left, int right, int item){
if (right >= left){
// calculation of new mid
int mid = left + (right - left)/2;
// returns position where found
if (array[mid] == item)
return mid+1;
// goes to recursive calls in left half
if (array[mid] > item)
return binarySearch(array, left, mid-1, item);
// goes to recursive calls in right half
else
return binarySearch(array, mid+1, right, item);
}
// if element is not found we return -1
else
return -1;
}
public static void main(String args[]){
int[ ] array = {10, 20, 30, 40, 50, 60, 70, 80};
int item = 70;
int size = array.length;
int position = binarySearch(array, 0, size-1, item);
if(position == -1)
System.out.println("Element not found");
else
System.out.println("The value " + item + " found at position: " + position);
}
}
// Time complexity O(Log N)
// Binary Search implementation in Java (Recursive)
// Time Complexity : O(N)
// Space Complexity : O(1)
// Auxiliary Space Complexity : O(N) due to function call stack
public class Main{
public static int binarySearch(int arr[], int left, int right, int item){
while (left <= right) {
int mid = left + (right - left) / 2;
// if item is at mid
if (arr[mid] == item)
return mid;
// If item greater, ignore left half, consider only right half
if (arr[mid] < item)
left = mid + 1;
// If item is smaller, ignore right half, consider only left half
else
right = mid - 1;
}
// if we are able to reach here
// means item wasn't present
return -1;
}
public static void main(String args[]){
int[ ] array = {10, 20, 30, 40, 50, 60, 70, 80};
int item = 70;
int size = array.length;
int position = binarySearch(array, 0, size-1, item);
if(position == -1)
System.out.println("Element not found");
else
System.out.println("The value " + item + " found at position: " + position);
}
}
Output
The value 70 found at position: 6
Time Complexity
For Binary Search
Best
O(1)
Average
O(log n)
Worst
O(log n)
Space Complexity
O(1)
Searching
Searching algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.
Login/Signup to comment