Binary search

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've narrowed down the possible locations to just one.

Here is an example of a binary search algorithm implemented in Python:

code

def binary_search(arr, x):

low = 0

high = len(arr) - 1

mid = 0

while low <= high:

mid = (high + low) // 2

# If x is greater, ignore left half

if arr[mid] < x:

low = mid + 1

# If x is smaller, ignore right half

elif arr[mid] > x:

high = mid - 1

# x is present at mid

else:

return mid

# If we reach here, then the element was not present

return -1

# Test array

arr = [2, 3, 4, 10, 40]

x = 10

# Function call

result = binary_search(arr, x)

if result != -1:

print("Element is present at index", str(result))

else:

print("Element is not present in array")

Explanation of above code

This code will search for the value 10 in the given array and return the index where it is found. If the element is not found, it will return -1.

It's important to note that, in order to use the binary search algorithm, the input list must be sorted.

binary search in c

Here is an example of a binary search algorithm implemented in C:

code

#include <stdio.h>

int binarySearch(int arr[], int l, int r, int x)

{

while (l <= r) {

int m = l + (r - l) / 2;

if (arr[m] == x)

return m;

if (arr[m] < x)

l = m + 1;

else

r = m - 1;

}

return -1;

}

int main(void)

{

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

int x = 10;

int n = sizeof(arr) / sizeof(arr[0]);

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

(result == -1) ? printf("Element is not present in array")

: printf("Element is present at index %d", result);

return 0;

}

Explanation of above code

This code will search for the value 10 in the given array and return the index where it is found. If the element is not found, it will return -1.

It's important to note that, in order to use the binary search algorithm, the input list must be sorted.

Also, in C, the function is defined with three extra parameter, left, right and x which is the element to be searched.

Binary search in java

Here is an example of a binary search algorithm implemented in Java:

code

class BinarySearch {

public static int binarySearch(int[] arr, int x) {

int left = 0;

int right = arr.length - 1;

while (left <= right) {

int middle = left + (right - left) / 2;

if (arr[middle] == x) {

return middle;

} else if (arr[middle] < x) {

left = middle + 1;

} else {

right = middle - 1;

}

}

return -1;

}

public static void main(String[] args) {

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

int x = 10;

int result = binarySearch(arr, x);

if (result == -1) {

System.out.println("Element is not present in array");

} else {

System.out.println("Element is present at index " + result);

}

}

}

Explanation of above code

This code will search for the value 10 in the given array and return the index where it is found. If the element is not found, it will return -1.

It's important to note that, in order to use the binary search algorithm, the input array must be sorted.

Also, in java, the function is defined with one parameter which is the element to be searched and the array is passed as an argument while calling the function.