[go: up one dir, main page]

0% found this document useful (0 votes)
33 views7 pages

G4 Dsa

The document discusses the binary search algorithm, including its time complexity, how it works, examples of its implementation in C#, and references for more information. It provides details on applying binary search, the iterative and recursive implementations, and examples of best and worst case scenarios.
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
33 views7 pages

G4 Dsa

The document discusses the binary search algorithm, including its time complexity, how it works, examples of its implementation in C#, and references for more information. It provides details on applying binary search, the iterative and recursive implementations, and examples of best and worst case scenarios.
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 7

Group 4

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.

Conditions for when to apply Binary Search in a Data Structure:


To apply Binary Search algorithm:
 The data structure must be sorted.
 Access to any element of the data structure takes constant time.
Binary Search Algorithm:
In this algorithm,
 Divide the search space into two halves by finding the middle index “mid”.
Finding the middle index “mid” in Binary Search Algorithm
 Compare the middle element of the search space with the key.
 If the key is found at middle element, the process is terminated.
 If the key is not found in the middle element, choose which half will be used as
the next search space.
 If the key is smaller than the middle element, then the left side is used for the
next search.
 If the key is larger than the middle element, then the right side is used for the
next search.
 This process is continued until the key is found or the total search space is
exhausted.

-Who discovered it?


The binary search algorithm was discovered independently by several researchers.
Among them were P.F. Windley, Andrew Donald Booth, Andrew Colin, and Thomas N.
Hibbard. The algorithm is also attributed to Conway Berners-Lee and David Wheeler,
who used it for storing labeled data in magnetic tapes in 1960. Additionally, the great
ancient Greek mathematician Euclid is often credited with formulating an early version
of the binary search algorithm in the third century BCE. This early version, known as the
“method of exhaustion,” involved iteratively dividing a range in half until the desired
value was found.

-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.

-Sample program of the algorithm (C#)


How to Implement Binary Search?
The Binary Search Algorithm can be implemented in the following two ways
 Iterative Binary Search Algorithm
 Recursive Binary Search Algorithm

Iterative Binary Search Algorithm:


Here we use a while loop to continue the process of comparing the key and splitting the
search space in two halves.

// C# implementation of iterative Binary Search


using System;

class GFG {

// Returns index of x if it is present in arr[]


static int binarySearch(int[] arr, int x)
{
int l = 0, r = arr.Length - 1;
while (l <= r) {
int m = l + (r - l) / 2;

// Check if x is present at mid


if (arr[m] == x)
return m;

// If x greater, ignore left half


if (arr[m] < x)
l = m + 1;

// If x is smaller, ignore right half


else
r = m - 1;
}

// If we reach here, then element was


// not present
return -1;
}

// 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);
}
}

Output: Element is present at index 3

Recursive Binary Search Algorithm:


Create a recursive function and compare the mid of the search space with the key. And
based on the result either return the index where the key is found or call the recursive
function for the next search space.
// C# implementation of recursive Binary Search
using System;

class GFG {

// Returns index of x if it is present in


// arr[l..r], else return -1
static int binarySearch(int[] arr, int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;

// If the element is present at the


// middle itself
if (arr[mid] == x)
return mid;

// If element is smaller than mid, then


// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, r, x);
}

// We reach here when element is not present


// in array
return -1;
}

// Driver code
public static void Main()
{

int[] arr = { 2, 3, 4, 10, 40 };


int n = arr.Length;
int x = 10;

int result = binarySearch(arr, 0, n - 1, x);

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

You might also like