## Search a sorted list with interspersed empty slots

Question 42. Consider the sorted array of strings A= {“”, “apple”, “”, “”, “ball”, “cat”, “”, “dog”, “”, “”, “”, “egg”, “”}. The array has empty strings interspersed in it. How will you efficiently search for strings in such an array?

We can use binary search to search the array of sorted strings. However since the array has empty strings in it, suppose we hit an empty string during binary search, we won’t know how to continue the search. To solve this problem we slightly modify the binary search and use the following strategy:

1. Binary search will occur between indexes low and high. If A[high] is an empty string, then we go on decrementing high till A[high] is a non-empty string. (Suppose we don’t find a non-empty string and we reach A[low], then all elements between low and high are empty strings. So we simply return indicating the search string was not found.)

2. We then find the mid element between low and high. If A[mid] is a non-empty string, then we proceed with the usual binary search. If A[mid] however is an empty string, then we go on incrementing mid till A[mid] is a non-empty string. Since A[high] already has a non-empty string, we will surely find a non-empty string when we keep incrementing mid.

## C/C++

```
/*
strings: sorted array of strings in which some of the strings can be empty ("")
num_strings: number of strings present (including empty strings)
x: string to be searched
Returns: index of x in the array strings if found, -1 otherwise
*/
int search(char *strings[], int num_strings, char *x)
{
int mid, result;
int low = 0;
int high = num_strings - 1;

while (low <= high) {
/*If we hit an empty string at position high, then keep decreasing
high till we get a non-empty string*/
while (low <= high && strcmp(strings[high], "") == 0) {
--high;
}

/*If we have only empty strings between low and high, then return
if (low > high)
return -1;
mid = (low + high) / 2;

/*If we get an empty element at mid, then keep incrementing mid.
We are guaranteed to find a non-empty string since strings[high]
is non-empty*/
while (strcmp(strings[mid], "") == 0)
mid = mid + 1;

/*Compare the mid element with the element being searched*/
result = strcmp(strings[mid], x);

if (result == 0) {
return mid;
} else if (result < 0) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}

```

## Java

```
/*
strings: sorted array of strings in which some of the strings can be empty ("")
x: string to be searched
Returns: index of x in the array strings if found, -1 otherwise
*/
public static int search(String[] strings, String x) {
int low = 0;
int high = strings.length - 1;

while (low <= high) {
/*If we hit an empty string at position high, then keep
decreasing high till we get a non-empty string*/
while (low <= high && strings[high] == "")
--high;

/*If we have only empty strings between low and high, then return
if (low > high)
return -1;

int mid = (low + high) / 2;

/*If we get an empty element at mid, then keep incrementing mid.
We are guaranteed to find a non-empty string since strings[high]
is non-empty*/
while (strings[mid] == "")
mid = mid + 1;

/*Compare the mid element with the element being searched*/
int result = strings[mid].compareTo(x);

if (result == 0) {
return mid;
} else if (result < 0) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}

```

## Python

```
#strings: sorted list of strings in which some of the strings can be empty ('')
#x: string to be searched
#Returns: index of x in the strings list if found, -1 otherwise
def search(strings, x) :
low = 0
high = len(strings) - 1

while (low <= high) :
#If we hit an empty string at position high, then keep decreasing
#high until we get a non-empty string
while (low <= high and strings[high] == '') :
high = high - 1

#If we have only empty strings between low and high, then return
if (low > high):
return -1

mid = (low + high) // 2

#If we get an empty element at mid, then keep incrementing mid.
#We are guaranteed to find a non-empty string since strings[high]
#is non-empty
while (strings[mid] == ''):
mid += 1

#Compare the mid element with the element being searched
if (strings[mid] == x) :
return mid
elif (strings[mid] < x) :
low = mid + 1
else :
high = mid - 1

return -1

```

## Find the first element larger than k in a sorted array

Question 41. Find the first element larger than k in a sorted array

Consider the sorted array A = {10, 20, 20, 30, 40, 50}. The first element larger than 25 is 30. In normal binary search, we search for a particular element and stop when we find the element. When we are trying to find the first element larger than k, k may not even exist in the array. So we instead use a modified form of binary search where we keep track of the first element larger than k as we search the array. The time complexity is O(logn). The code is given below

## C/C++

```
/*
a: sorted array containing elements in non-decreasing order
length: number of elements in the array
k: we are searching for the number immediately above k
Returns: the number immediately greater than k in the array if it exists,
MAX_INT otherwise
*/
int find_next_higher(int a[], int length, int k)
{
int low, high, mid, result;

low = 0;
high = length - 1;

result = MAX_INT;
while (low <= high) {
mid = (low + high) / 2;

if (a[mid] > k) {
result = a[mid]; /*update the result and continue*/
high = mid - 1;
} else {
low = mid + 1;
}
}

return result;
}

```

## Java

```
/*
a: sorted array containing elements in non-decreasing order
k: we are searching for the number immediately above k
Returns: the number immediately greater than k in the array if it exists,
MAX_INT otherwise
*/
public static int findNextHigher(int[] a, int k) {
int low = 0;
int high = a.length - 1;

int result = MAX_INT;
while (low <= high) {
int mid = (low + high) / 2;

if (a[mid] > k) {
result = a[mid]; /*update the result and continue*/
high = mid - 1;
} else {
low = mid + 1;
}
}

return result;
}

```

## Python

```
#a: sorted list containing elements in non-decreasing order
#k: we are searching for the number immediately above k
#Returns: the number immediately greater than k in the list if it exists,
#		MAX_INT otherwise
def find_next_higher(a, k) :
low = 0
high = len(a) - 1

result = MAX_INT
while (low <= high) :
mid = (low + high) // 2

if (a[mid] > k) :
result = a[mid] #update the result and continue
high = mid - 1
else :
low = mid + 1

return result

```

## Find the first occurrence of an element in a sorted array

Question 40. Find the first occurrence of a number in a sorted array

Consider the sorted array A = {10, 10, 20, 20, 30, 30, 30}. If we are asked to return the first occurrence of 30, then we return the index 4. If we are asked to return the first occurrence of a number not present in the array such as 15, then we return -1.

We can do this using modified binary search in O(logn). In normal binary search, we stop as soon as we find the element being searched. In the modified binary search, we continue the binary search if the found element is not the first occurrence of the element in the array. The code is given below

## C/C++

```
/*
a: array being searched
n: number of elements in array
x: element being searched
Return value: first position of x in a, if x is absent -1 is returned
*/
int find_first(int a[], int n, int x)
{
int start, end, mid;

start = 0;
end = n - 1;

while (start <= end) {
mid = (start + end) / 2;

if (a[mid] == x) {
if (mid == 0 || a[mid - 1] != x)
return mid;
else
end = mid - 1;

} else if (a[mid] > x) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}

```

## Java

```
/*
a: array being searched
x: element being searched
Return value: first position of x in a, if x is absent -1 is returned
*/
public static int findFirst(int[] a, int x) {
int n = a.length;
int start = 0;
int end = n - 1;

while (start <= end) {
int mid = (start + end) / 2;

if (a[mid] == x) {
if (mid == 0 || a[mid - 1] != x)
return mid;
else
end = mid - 1;

} else if (a[mid] > x) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}

```

## Python

```
#a: list being searched
#x: element being searched
#Return value: first position of x in a, if x is absent -1 is returned
def find_first(a, x) :
n = len(a)
start = 0
end = n - 1

while (start <= end) :
mid = (start + end) // 2

if (a[mid] == x) :
if (mid == 0 or a[mid - 1] != x):
return mid
else:
end = mid - 1

elif (a[mid] > x) :
end = mid - 1
else :
start = mid + 1

return -1

```

## Find max and min using least operations

Question 39. Find the maximum and minimum elements in an array using the least number of comparisons

In the simple approach, we will compare each element of the array with the maximum value and minimum value obtained so far. So for every element, we need 2 comparisons.

In the efficient approach, we pick all pairs of consecutive numbers in the array and first compare the numbers within each pair. Then we compare the highest in the pair with the maximum value and the lowest in the pair with the minimum value. So we need 3 comparisons for 2 elements instead of 4 comparisons needed by the simple approach.

Since we will be picking pairs of consecutive numbers, if we have odd number of elements in the array, the last element will be left unpaired. To avoid this problem, if we have odd elements, we will initialize the max value and the min value to the first element in the array and then go on picking pairs of numbers from the second element onwards.

## C/C++

```
/*a:input array
length: number of elements in array a
min_value: the minimum value is returned here
max_value: the maximum value is returned here*/
void find_min_max(int a[], int length, int *min_value, int *max_value) {
int i = 0;
*max_value = MIN_INT;
*min_value = MAX_INT;
if (length % 2 == 1) {
/*If there are odd number of elements, then initialize
max_value and min_value with a[0]*/
*max_value = *min_value = a[0];
i = 1;
}

for (; i < length; i += 2) {
if (a[i] > a[i+1]) {
if (a[i] > *max_value)
*max_value = a[i];
if (a[i+1] < *min_value)
*min_value = a[i+1];
} else {
if (a[i] < *min_value)
*min_value = a[i];
if (a[i+1] > *max_value)
*max_value = a[i+1];
}
}
}

```

## Java

```
/*a:input array
result: the minimum value is returned in result[0] and
the maximum value is returned in result[1]*/
public static void findMinMax(int[] a, int[] result) {
int length = a.length;
int maxValue = MIN_INT;
int minValue = MAX_INT;
int i = 0;
if (length % 2 == 1) {
/*If there are odd number of elements, then initialize
maxValue and minValue with a[0]*/
maxValue = minValue = a[0];
i = 1;
}

for (; i < length; i += 2) {
if (a[i] > a[i+1]) {
if (a[i] > maxValue)
maxValue = a[i];
if (a[i+1] < minValue)
minValue = a[i+1];
} else {
if (a[i] < minValue)
minValue = a[i];
if (a[i+1] > maxValue)
maxValue = a[i+1];
}
}
result[0] = minValue;
result[1] = maxValue;
}

```

## Python

```
#a: input list
#Returns: the minimum value and maximum value in list are returned
def find_min_max(a) :
length = len(a)
max_value = MIN_INT
min_value = MAX_INT

i = 0
if (length % 2 == 1) :
#If there are odd number of elements, then initialize
#max_value and min_value with a[0]
max_value = min_value = a[0]
i = 1

while ( i < length ) :
if (a[i] > a[i+1]) :
if (a[i] > max_value) :
max_value = a[i]
if (a[i+1] < min_value):
min_value = a[i+1]
else :
if (a[i] < min_value):
min_value = a[i]
if (a[i+1] > max_value):
max_value = a[i+1]

i += 2

return min_value, max_value

```

## Find the smallest and second smallest

Question 38. Find the smallest and second smallest numbers in an array

We can find the smallest and second smallest numbers in a single scan of the array. We will maintain another array called min_values for storing the 2 smallest numbers. min_values[0] will store the smallest value and min_values[1] will store the second smallest value. min_values[0] and min_values[1] are initialized to MAX_INT. As we traverse the main array, we do the following

– If the current element is smaller than min_values[0], then we move min_values[0] to min_values[1] and store the current element in min_values[0]

– If the current element is larger than min_values[0] but smaller than min_values[1], then we store the current element in min_values[1]

The code is given below:

## C/C++

```
/*
a:input array
length: number of elements in array a
min_value: the two smallest values will be returned here
*/
void find_two_smallest(int a[], int length, int min_value[])
{
int i;

min_value[0] = min_value[1] = MAX_INT;

for (i = 0; i < length; ++i) {
if (a[i] < min_value[0]) {
min_value[1] = min_value[0];
min_value[0] = a[i];
} else if (a[i] < min_value[1]) {
min_value[1] = a[i];
}
}
}

```

## Java

```
/*
a:input array
minValue: the two smallest values will be returned here
*/
public static void findTwoSmallest(int[] a, int[] minValue) {
minValue[0] = minValue[1] = MAX_INT;

for (int curVal : a) {
if (curVal < minValue[0]) {
minValue[1] = minValue[0];
minValue[0] = curVal;
} else if (curVal < minValue[1]) {
minValue[1] = curVal;
}
}
}

```

## Python

```
#a:input list
#Return value: the two smallest values will be returned
def find_two_smallest(a) :
length = len(a)

min_value = [MAX_INT, MAX_INT]

for  cur_val in a:
if (cur_val < min_value[0]) :
min_value[1] = min_value[0]
min_value[0] = cur_val
elif (cur_val  < min_value[1]) :
min_value[1] = cur_val

return min_value[0], min_value[1]

```