Assignment 1 in course Data Structures
An array V of size m initially contains n sorted natural numbers, while the rest of the array There are zeros. Suppose the size n is unknown.
Write a program that receives as input the array V, its size m and an additional natural number x. The program must return the index of the number x in the array, or alternatively return -1 if the number Does not exist in the array.
For this, write 3 routines:
- Search1(V,m,x) in O(n) runtime complexity.
- Search2(V,m,x) in O(logm) runtime complexity.
- Search3(V,m,x) in O(logn) runtime complexity.