what is binary search in data structure

 what is binary search in data structure?

In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array.

What is binary search?

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item until you have narrowed down the possible locations to just one.

What is meant by binary search in data structure?

Binary search is a fast search algorithm with run-time complexity of Ο(log n). ... For this algorithm to work properly, the data collection should be in the sorted form. A binary search looks for a particular item by comparing the middle-most item of the collection. If a match occurs, then the index of the item is returned.

We basically ignore half of the elements just after one comparison.

Compare x with the middle element.

If x matches with the middle element, we return the mid index.

Else If x is greater than the mid element, then x can only lie in the right half subarray after the mid element. So we recur for the right half.

Else (x is smaller) recur for the left half.

C#  binary Example:

// 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 method to test above

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 not present");

else

Console.WriteLine("Element found at index "

+ result);

}

}

// This code is contributed by Sam007.