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

Pigeonhole Sort

Pigeonhole sort is a sorting algorithm that works by distributing elements of an input sequence into a set of pigeonholes or buckets. It is an efficient sorting algorithm for small ranges of values where the number of elements to be sorted is roughly the same as the range of values. Pigeonhole sort is an example of a bucket sort algorithm. The pigeonhole sort algorithm works by first determining the range of values in the input sequence. This range is used to create a set of pigeonholes or buckets, each of which can hold one or more elements from the input sequence. Each element in the input sequence is then placed into its corresponding pigeonhole based on its value. If two or more elements have the same value, they can be placed in the same pigeonhole. Once all the elements have been placed into their corresponding pigeonholes, the elements are sorted within each pigeonhole. Finally, the sorted elements are combined into a single output sequence. Pigeonhole sort has a time complexity...
Post a Comment
Read more

Counting Sort

Counting sort is a sorting algorithm that operates by counting the frequency of each element in the input array, and then using these frequencies to compute the final sorted output. The algorithm works by first creating an array of counters, with each counter corresponding to a distinct element in the input array. The counters are initialized to zero, and then the input array is scanned once to count the number of occurrences of each element. This count information is stored in the corresponding counter in the counter array. Once the count information is obtained, the algorithm uses it to determine the final position of each element in the sorted output array. This is done by iterating over the counter array, and for each counter value, writing the corresponding element to the sorted output array the appropriate number of times. The time complexity of counting sort is O(n+k), where n is the length of the input array and k is the range of the elements. The space complexity is also O(n+k...
2 comments
Read more

Selection Sort

Selection sort is a simple sorting algorithm that sorts an array by repeatedly finding the minimum element from the unsorted portion of the array and swapping it with the first element of the unsorted portion. It is called selection sort because it repeatedly selects the smallest element of the unsorted portion of the array and moves it to its correct position in the sorted portion of the array. The time complexity of selection sort is O(n^2), where n is the number of elements in the array. This makes it inefficient for large arrays and it is not a good choice for sorting large datasets. However, selection sort is easy to understand and implement, and it is useful for educational purposes and for small arrays. One of the advantages of selection sort is that it makes fewer swaps than other sorting algorithms such as bubble sort. This makes it more efficient in terms of memory writes, which can be important in some situations. Another advantage of selection sort is that it is a stable so...
2 comments
Read more