Binary Search is an efficient algorithm for locating a target element in a sorted array by repeatedly dividing the search interval in half.
left to the start of the array and right to the end.mid = left + (right - left) / 2;
mid equals the target, return mid (target found).mid is less than the target, update left to mid + 1 to search the right half.mid is greater than the target, update right to mid - 1 to search the
left half.4.Repeat
left exceeds right.-1.| Scenario | Time Complexity | Explanation |
|---|---|---|
| Best Case | O(1) | The target is found at the middle in the first try. |
| Average Case | O(log n) | The search space is halved with each iteration. |
| Worst Case | O(log n) | Even in the worst case, the number of comparisons grows logarithmically. |
https://drawtocode.vercel.app/problems/binary-search
Loading component...
Loading component...
INPUT: [1,2,3,4,5] ,3
OUTPUT: 2
public static void main(String args[]){
int arr[] = { 1,2,3,4,5 };
int ans = binarySearch( arr,5);
if (ans == -1) {
System.out.print("Element is not present in array");
}//If End
else {
System.out.print("Element is present at index " + ans );
}//Else End
}//function end
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}//If End
else{
if (arr[mid] < target) {
left = mid + 1;
}//If End
else {
right = mid - 1;
}//Else End
}//Else End
}//Loop End
return -1;
} //function end
Utility Function is not required.