### Binary Search for infinite array

Binary Search for Infinite Array

Problem:- Given an array of integer write an algorithm to find the element entered by the user for searching. Take input from the user and return the index of the element (Array size in unknown).

`input:`

`arr[] = {3, 5, 7, 9, 10, 90, 100, 130,`

`140, 160, 170}`

Enter the element which is to searched :- 90 Output: Element found at index: 6

As we know that binary search can be applied to the array whose size is known to us.

However, if we want to apply binary search to an infinite array , then what should we do ,because for applying binary search we should know the size of the array.( What if we want to search element in an infinite array).

The answer is quite sure that we will apply binary search to solve this question.

We will find the proper bounds to search the elements in the array.

Algorithm:- Step 1:- Mark the low variable point to the starting element of the array and high variable to the second element of the array i.e low=0 and high=1; Step 2:- Compare the key with the following conditions:- If the key is greater than the high , then change the high to low and double the high variable. If the key is lower than high index value , then apply the binary search on the given high and low indexes.

Now lets us get through with the code:-

Code is compile and run in Turbo c++.

Code:-

#include<iostream.h> using namespace std; int binarySearch(int ar[], int low,int high, int key) { while (low <= high) { int mid = low + (high-low)/2; // check if key is the mid element if (arr[mid] == key) return mid; // If key is greater, ignore left half if (arr[mid] < key) low = mid + 1; // If key is smaller, ignore right half else high = mid - 1; } return -1; } int pos_find(int ar[],int key) { low=0, high=1; int curr_val=ar[0]; while(low<key) { low=high; //update the low high=2*high; //double the high index curr_val=ar[high]; // and update the curr_val for comparsion } binarysearch(ar,low,high,key); //calling the binary search function } int main() { int n,key; cout<<”Enter the size of the array:”; cin>>n; int ar[n]; cout<<”Enter the key to search”; cin>>key; int result = binarySearch(ar, 0, n-1, key); (result == -1)? printf("Element is not presentin array") : printf("Element is present at index %d", result); return 0; }

Time complexity:- The time complexity of the above algorithm will be O(logn).

CommentsNo comment yet.