Range Search

Given an sorted array of integers, perform binary search to find the index of the range in which the number lies. A range is specified by index of its lower bound.

Example :

array 12 20 32 40 52

          ^   ^   ^   ^   ^

index  0   1   2   3   4

Given the number -> 19 (It lies between index 0 and 1), return 0
Given the number -> 22 (It lies between index 1 and 2), return 1
Given the number -> 40 (It lies between index 3 and 4), return 3

Solution
Use binary search.

Suppose we are at index i , then there are two possibilities:

A[i] < N , this implies that we need to check in (i+1, N)
• A[i] >= N   this implies that we need to check in (0, i)

Code

int range_search(int array[], int N, int begin, int end){

if(begin > end)

return -1;

     
int mid=(begin + end)/2;
     
if(array[mid] > N){

if(array[mid-1] <= N)

return mid-1;

else

return range_search(array, N, begin, mid-1);

}
else if(array[mid] <= N){

if(array[mid+1] > N)

return mid;

else

return range_search(array, N, mid+1, end);

} 

}

Complexity

• Time : O(log N)
• Space : O(1)

Fixed Point

Given an array of N distinct integers sorted in ascending order, write a function that returns a Fixed Point in the array, if there is any Fixed Point present in array, else returns -1. Fixed Point in an array is an index i such that arr[i] is equal to i. Note that integers in array can be negative.

Examples :

Input: arr[] = {-10, -5, 0, 3, 7}
Output: 3 // arr[3] == 3

Input: arr[] = {0, 2, 5, 8, 17}
Output: 0 // arr[0] == 0

Input: arr[] = {-10, -5, 3, 4, 7, 9}
Output: -1 // No Fixed Point

Solution

Use binary search to find out such an element where array[i] == i.

Suppose we are at index i , then there are three possibilities:

• A[i] < i , this implies that all the numbers at index less than i cannot be fixed, so we need to check in the interval (i+1, N)
• A[i] > i this implies that all the numbers at index greater than i cannot be fixed, so we need to check in the interval (0, i - 1) 
• A[i] == i this implies that the number is fixed , so output it.

Code
int fixed_point(int array[], int begin, int end){

if(begin > end)

return -1;

int mid = (begin + end)/2;

if(array[mid] > mid)

return fixed_point(array, begin, mid-1);

else if(array[mid]<mid)

return fixed_point(array, mid+1, end);

else

return mid;

}

Complexity

• Time : O(log N)
• Space : O(1)

Subarray with Specific Sum

Given an unsorted array of nonnegative integers, find a continuous subarray which adds to a given number.

Examples:

Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33
Output: Sum found between indexes 2 and 4

Input: arr[] = {1, 4, 0, 0, 3, 10, 5}, sum = 7
Output: Sum found between indexes 1 and 4

Input: arr[] = {1, 4}, sum = 0
Output: No subarray found

There may be more than one subarrays with sum as the given sum. Print first such subarray.

Solution

1. Take two indices start and end denoting the starting and ending index.,which initially point to first element A[0] and a variable sum which stored the current sum (=A[0]).
2. Now increase end until and unless sum becomes greater than required sum S. This is done because we cannot find S in a subarray whose maximum sum is less than S.
3. Now once sum becomes greater than S, we have chance to find a subarray with ending point as end. Therefore we can increase start until it is not greater than sum . Once it becomes smaller ,we are back to step 2. Now if no subarray exists for which sum is S, start will be eventually equal to end, so now the new problem will be array starting at start+1 and ending at end+1.

Code

int subarray_sum(int array[], int N, int S, int &start, int &end){

start = end = 0;
while(end < N && start < N){

while(current_sum < sum && end < N)

current_sum += array[end++];

while(current_sum > sum && start < N){

current_sum -= array[start++];

if(current_sum == sum)

return 1;

}

}
return 0;

}

Complexity

• Time : O(N)
• Space : O(1)

Constant Boundary Separation

Given an integer k and an sorted array A (can consist of both positive and negative numbers), output 2 integers from A such that a-b=k in O(n) time and O(1) space.

Solution

Idea is to take two indices i and j which initially point to the last element.Then

• If their difference is equal to K ,then output the required answer.
• If it is less than K , then only possible way is decreasing i , 
• If it is greater than K , then only possible way is decreasing j.

Code
int boundary(int array[], int N, int K, int *a, int *b){

int i = j = N -1;
while(i >= 0 && j < N && i <= j){

if(array[j] - array[i] == K){

*a = array[j];
*b = array[i];

return 1;

}
else if(array[j] = array[i] > K)

j--;

else

i--;

}
return 0;

}

Complexity

• Time : O(N)
• Space : O(1)