Binary Search algorithm – Data Structure and Algorithm

Binary search is an algorithm used to find the position of a target value within a sorted array. The algorithm works by repeatedly dividing the search interval in half and comparing the target value to the middle element of the array. If the target value matches the middle element, the search is successful. Otherwise, the search continues in the lower or upper half of the array, depending on whether the middle element is greater or less than the target value.

Binary search is a commonly used search algorithm in computer science that works by repeatedly dividing the search interval in half. It is a very efficient algorithm for searching sorted arrays or lists.

Here's how binary search works:

1. Given a sorted list of elements, the algorithm compares the target value to the middle element of the list.

2. If the target value is equal to the middle element, the search is complete and the index of the middle element is returned.

3. If the target value is less than the middle element, the search continues on the lower half of the list.

4. If the target value is greater than the middle element, the search continues on the upper half of the list.

5. The search interval is halved at each iteration until the target value is found or the search interval is empty.

Here's an example of how binary search works:

Suppose you have a sorted array of integers as follows:

let arr = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

And you want to find the position of the value 10 in the array.

1. Start by defining two pointers: left and right. Set left to the first index of the array (which is 0) and right to the last index of the array (which is 9).
2. Calculate the middle index of the array as mid = (left + right) // 2 (integer division).
3. Compare the target value (10) with the middle element of the array (arr[mid]). In this case, arr[mid] is 10, so the search is successful and we return mid.
4. If the target value is less than the middle element (arr[mid]), then set right to mid - 1 and repeat step 2.
5. If the target value is greater than the middle element (arr[mid]), then set left to mid + 1 and repeat step 2.

For example, let's say we want to find the position of the value 16 in the array:

1. left = 0, right = 9.
2. mid = (0 + 9) // 2 = 4.
3. arr[mid] = 10 is less than 16, so we set left = mid + 1 = 5 and repeat step 2.
4. mid = (5 + 9) // 2 = 7.
5. arr[mid] = 16 is equal to the target value, so we return mid = 7.

Binary search has a time complexity of O(log n), which makes it very efficient for large lists or arrays.

Leave a comment