Question:
Given an array in descending order and a key. You need to check if the key is present or not using binary search.
Example:
Array = 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
Key = 2
Output: Key is found.
Solution:
Solution is very simple.
First we calculate the mid index, and then we check the element at mid index is equal to the key. If it is equal, then we return TRUE.
If it is not equal, then we check if the key element is less than the mid, if it is less than mid element, then we traverse towards right.
Else we traverse towards left.
Usually when the array is sorted in ascending order, we do it in reverse.
This is a slight variation of binary search
Solution in C++
#include <iostream> using namespace std; int binary_search(int arr[], int start, int end, int key) { while (start <= end) { int mid = start + (end - start) / 2; // Check if key is present at mid if (arr[mid] == key) return mid; // If key greater, ignore right half if (arr[mid] < key) end = mid - 1; // If key is smaller, ignore left half else start = mid + 1; } // if we reach here, then element was // not present return -1; } int main(void) { int arr[] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; int key = 2; int size = sizeof(arr) / sizeof(arr[0]); int result = binary_search(arr, 0, size - 1, key); if(result == -1) { cout << "Key is not present in array"<<endl; } else { cout << "Key is present at index " << result<<endl ; } return 0; }
Output
Key is present at index 8