Skip to main content

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.

Comments

Post a Comment

Popular posts from this blog

Bubble Sort

   Bubble sort is a simple sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. It is named after the way bubbles rise to the top of a liquid, as it sorts the array by repeatedly moving the largest or smallest elements to the top of the array. The algorithm works by iterating through the array, comparing each adjacent pair of elements and swapping them if they are in the wrong order. This process is repeated until the array is fully sorted. Let's say we have an array of integers [5, 3, 8, 4, 2]. The first pass of the algorithm would compare 5 and 3, swap them to get [3, 5, 8, 4, 2]. It would then compare 5 and 8 and not swap them, as they are in the correct order. It would then compare 8 and 4, swap them to get [3, 5, 4, 8, 2]. It would then compare 8 and 2, swap them to get [3, 5, 4, 2, 8]. The first pass is now complete, and the largest element, 8, is at the end of the array. The second pass would start with comparing 3 and 5,...
Post a Comment
Read more

Shell Sort

Shell sort is a sorting algorithm developed by Donald Shell in 1959. It is an extension of the insertion sort algorithm and is classified as an in-place comparison sort. Shell sort aims to improve the performance of insertion sort by sorting elements that are far apart from each other first, thus reducing the number of comparisons needed to sort the entire array. The algorithm works by first dividing the array into smaller subarrays, each containing elements that are a certain gap apart. The gap is typically initialized to be the length of the array divided by 2, and is then halved in each iteration until it becomes 1. The subarrays are then sorted using insertion sort, which sorts elements within each subarray by comparing adjacent elements and swapping them if they are in the wrong order. The key idea behind Shell sort is that insertion sort performs poorly on arrays that are almost sorted, but works well on small arrays. By sorting the subarrays with larger gaps first, the algorithm...
Post a Comment
Read more

Comb Sort

Comb sort is a sorting algorithm that was first proposed by WÅ‚odzimierz Dobosiewicz in 1980. The algorithm is a variation of bubble sort, and it is designed to improve upon the performance of bubble sort by using a larger gap between elements during the comparison phase of the algorithm. The basic idea behind comb sort is to compare elements that are separated by a large gap, and gradually reduce the gap between elements until the gap is equal to 1. The gap between elements is known as the "comb" in comb sort, and it is initially set to be the size of the input array being sorted. The size of the comb is then reduced by a factor known as the shrink factor, which is typically set to 1.3. During each pass of the algorithm, elements that are separated by the current gap are compared and swapped if they are out of order. The gap between elements is then reduced by the shrink factor, and the process is repeated until the gap is equal to 1. Once the gap is equal to 1, the algorithm...
Post a Comment
Read more