G4 Dsa
G4 Dsa
Short Description
-What is the algorithm all about?
Binary Search is defined as a searching algorithm used in a sorted array by
repeatedly dividing the search interval in half. The idea of binary search is to use the
information that the array is sorted and reduce the time complexity to O (log N).
Binary search algorithm is a method of finding an element’s position in a sorted array by
repeatedly comparing the target value with the middle element of the array and dividing
the search space in half. It is a fast and efficient way of searching for data that runs in
logarithmic time in the worst case.
-State in what specific scenario the best case and worst case of algorithm
The best-case scenario for a binary search algorithm occurs when the target value is
located at the middle of the sorted array. In this case, the algorithm finds the target
value in the first comparison. The best case time complexity is O (1), which means it
takes constant time regardless of the size of the input.
The worst-case scenario for a binary search algorithm occurs when the target value is
located at one of the ends of the sorted array or is not in the array at all. In this case,
the algorithm must make the maximum number of comparisons, which is equal to the
height of the binary search tree. The worst-case time complexity is O (log n), where n is
the size of the input array. This means that the time it takes to find the target value
increases logarithmically with the size of the input.
class GFG {
// Driver code
public static void Main()
{
int[] arr = { 2, 3, 4, 10, 40 };
int n = arr.Length;
int x = 10;
int result = binarySearch(arr, x);
if (result == -1)
Console.WriteLine(
"Element is not present in array");
else
Console.WriteLine("Element is present at "
+ "index " + result);
}
}
class GFG {
// Driver code
public static void Main()
{
if (result == -1)
Console.WriteLine(
"Element is not present in arrau");
else
Console.WriteLine("Element is present at index "
+ result);
}
}
Output:Element is present at index 3
-References
Binary Search - Data Structure and Algorithm Tutorials - GeeksforGeeks
Algorithm for Binary Search - javatpoint