Binary Search

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing the search interval in half. The basic idea is to use the information that the array is sorted and reduce the time complexity to O(log n).

The algorithm begins by comparing the middle element of the array with the target value. If the target value matches the middle element, its position in the array is returned. If the target value is less than the middle element, the algorithm repeats its action on the sub-array to the left of the middle element. If the target value is greater than the middle element, the algorithm repeats its action on the sub-array to the right of the middle element.

The algorithm will then continue to the next step until the target value is found or the search interval is empty. The search interval is initially the whole array. If the target value is less than the middle element of the current array, the algorithm will search the left half of the array. If the target value is greater than the middle element of the current array, the algorithm will search the right half of the array.

The time complexity of the binary search algorithm is O(log n), where n is the number of elements in the array. This is because at each step of the algorithm, the size of the array is halved. The space complexity is O(1), as the algorithm only requires a few variables to keep track of the current search interval.

Binary search can also be used to find the position of the first or last occurrence of a target value in a sorted array with a few modifications. It can also be applied to other data structures such as linked lists, trees, and graphs.

Overall, binary search is a very efficient algorithm for searching in a sorted array, and it's widely used in many real-world applications. However, it's important to keep in mind that the array needs to be sorted for binary search to work correctly.

PSEUDO CODE:

This is a basic implementation of the binary search algorithm. It takes a sorted list and an item to search for as its inputs. The function uses two pointers, low and high, to keep track of the portion of the list that is still being searched. The middle element of the current search range is determined by taking the average of the low and high pointers, which is stored in the mid variable. If the middle element is equal to the item being searched for, the function returns its index. If the middle element is greater than the item being searched for, the search range is narrowed to the lower half of the list by moving the high pointer to be one less than the middle element. If the middle element is less than the item being searched for, the search range is narrowed to the upper half of the list by moving the low pointer to be one more than the middle element. If the low pointer becomes greater than the high pointer, the item being searched for is not in the list, and the function returns None.

PYTHON CODE:

Here is an example of binary search implemented in Python:

This is an example of a basic implementation of the binary search algorithm in Python. The function takes in a sorted list (arr) and a value to search for (x) as its parameters. It starts by setting the low and high pointers to the start and end of the list, respectively, and initializing a mid variable. Then, it enters a while loop that continues until the low pointer is greater than the high pointer. Within the while loop, it updates the mid variable to be the average of the low and high pointers, and then checks if the value at the mid index is less than, greater than, or equal to the target value (x). If the value at the mid index is less than x, it updates the low pointer to be one more than the current mid value. If the value at the mid index is greater than x, it updates the high pointer to be one less than the current mid value. If the value at the mid index is equal to x, it returns the mid value. If the while loop completes without finding the target value, the function returns -1 to indicate that the value was not present in the list.

JAVA CODE:

Here is an example of binary search implemented in Java:

This is an example of a basic implementation of the binary search algorithm in Java. The function binarySearch() takes in an array of integers (arr) and the value to be searched (x) as its parameters. It starts by initializing the left and right pointers to the start and end of the array, respectively. Then, it enters a while loop that continues until the left pointer is less than or equal to the right pointer. Within the while loop, it calculates the middle index using the formula mid = left + (right - left) / 2

It then compares the element at the middle index of the array with the target value(x). If the element at the middle index is equal to the target value, it returns the middle index. If the element at the middle index is less than the target value, it updates the left index to be one more than the current middle index. If the element at the middle index is greater than the target value, it updates the right index to be one less than the current middle index. If the while loop completes without finding the target value, the function returns -1 indicating that the target value is not present in the array.

In the main() function, an array of integers is defined and the value to be searched is assigned to the variable x. The binarySearch() function is called with the array and the value as arguments, and the result is stored in the variable result. The result is then checked and an appropriate message is printed to the console using the System.out.println() statement.

C CODE:

Here is an example of binary search implemented in C:

This is an example of a basic implementation of the binary search algorithm in C. The function binarySearch() takes in an array of integers (arr), the left (l) and right (r) indices and the value to be searched (x) as its parameters. The function checks if the right index is greater than or equal to the left index. If true, it calculates the middle index using the formula mid = l + (r - l) / 2.

It then compares the element at the middle index of the array with the target value(x). If the element at the middle index is equal to the target value, it returns the middle index. If the element at the middle index is greater than the target value, it calls the binarySearch() function again but this time with the right index being one less than the current middle index. If the element at the middle index is less than the target value, it calls the binarySearch() function again but this time with the left index being one more than the current middle index. If the right index is not greater than or equal to the left index, it returns -1 indicating that the target value is not present in the array.

In the main() function, an array of integers is defined and the value to be searched is assigned to the variable x. The size of the array is calculated and passed as the right index to the binarySearch() function. The function is called with left index as 0 and the result is stored in the variable result. The result is then checked and an appropriate message is printed.

C++ CODE:

Here is an example of binary search implemented in C++:

This is an example of a basic implementation of the binary search algorithm in C++. The function binarySearch() takes in an array of integers (arr), the left (left) and right (right) indices and the value to be searched (x) as its parameters. The function uses a while loop that continues until the left index is less than or equal to the right index. Within the while loop, it calculates the middle index using the formula mid = left + (right - left) / 2.

It then compares the element at the middle index of the array with the target value(x). If the element at the middle index is equal to the target value, it returns the middle index. If the element at the middle index is less than the target value, it updates the left index to be one more than the current middle index. If the element at the middle index is greater than the target value, it updates the right index to be one less than the current middle index. If the while loop completes without finding the target value, the function returns -1 indicating that the target value is not present in the array.

In the main() function, an array of integers is defined and the value to be searched is assigned to the variable x. The size of the array is calculated and passed as the right index to the binarySearch() function. The function is called with left index as 0 and the result is stored in the variable result. The result is then checked and an appropriate message is printed to the console using the cout statement.

JAVASCRIPT CODE:

Here is an example of binary search implemented in Javascript:

This is an example of a basic implementation of the binary search algorithm in JavaScript. The function binarySearch() takes in an array of integers (arr) and the value to be searched (x) as its parameters. It starts by initializing the left and right pointers to the start and end of the array, respectively. Then, it enters a while loop that continues until the left pointer is less than or equal to the right pointer. Within the while loop, it calculates the middle index using the formula Math.floor((left + right) / 2).

It then compares the element at the middle index of the array with the target value(x). If the element at the middle index is equal to the target value, it returns the middle index. If the element at the middle index is less than the target value, it updates the left index to be one more than the current middle index. If the element at the middle index is greater than the target value, it updates the right index to be one less than the current middle index. If the while loop completes without finding the target value, the function returns -1 indicating that the target value is not present in the array.

In the main code, an array of integers is defined and the value to be searched is assigned to the variable x. The binarySearch() function is called with the array and the value as arguments, and the result is stored in the variable result. The result is then checked and an appropriate message is printed to the console using the console.log() statement.