Vivekanand Vellanki
1

The question makes an assumption that the array is sorted. If the array is not sorted, binary search will not work.


Assuming that the array is sorted, there can be many techniques to find an element.


Linear search. Start from the first element and check each element until the element is found, or the end of array is reached. An optimisation is to stop if the array element is greater than the element searched.


Create indices. Before the advent of mobiles, people wrote phone numbers in a book. To be able to find someone's number from the book, the book was divided with separators for each alphabet - A, B, C and so on. This is similar to how multi-class notebooks have separators. If one wanted to find the phone number of "Trump", they would directly go to 'T' and look for Trump there.


A similar technique could be used.


Sharding. Assume you have a very large array, for e.g. the Aadhar database where given the Aadhar number one can access the name, address and other details. Even using binary search on such a large database (a billion people as of now) takes time.


An alternative is the following: divide the billion entries in the database into a large number of batches (e.g. 1000). For e.g. a simple technique would be to take N mod 1000 where N is the Aadhar number; and insert this entry into that particular database. Now, each database has approximately a million entries instead of one large database with a billion entries. Searching through the million is faster compared to searching through a billion.


This can be made faster by increasing 1000 to say 10,000 - this reduces the entries in a database to 100,000. The technique here was - use hashing to reduce the space in which one has to search and then use binary search or other techniques to search in the smaller space.