Question:

Given an array whose order of sorting is unknown and a key. You need to check if the key is present or not using binary search.

Solution:

As the question stated, we dont know the order of the array.

Our first step is to get to know the order of the array.

How do we do that?

Simple: We check the first and last element of the array.

If the first element is smaller than the last element, then it is in ascending order, else it is in descnding order.

Solution in C++

#include <iostream> using namespace std; int binary_search(int arr[], int start, int end, int key) { int ascending = 0; if (arr[start] < arr[end]) ascending = 1; while (start <= end) { int mid = start + (end - start) / 2; // Check if key is present at mid if (arr[mid] == key) return mid; if(ascending == 1) { // If key greater, ignore left half if (arr[mid] < key) start = mid + 1; // If key is smaller, ignore right half else end = mid - 1; } else { // 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) { //descending order 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 ; } //ascending order int arr_1[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int key_1 = 2; int size_1 = sizeof(arr) / sizeof(arr[0]); int result_1 = binary_search(arr_1, 0, size_1 - 1, key_1); if(result_1 == -1) { cout << "Key is not present in array"<<endl; } else { cout << "Key is present at index " << result_1<<endl ; } return 0; }

Output:

Key is present at index 8 Key is present at index 1