12

I'm trying to write an algorithm for finding the index of the closest value that is lesser than or equal to the search value in a sorted array. In the example of the array [10, 20, 30], the following search values should output these indexes:

  1. searchValue: 9, index: -1
  2. searchValue: 10, index: 0
  3. searchValue: 28, index: 1
  4. searchValue: 55555, index: 2

I want to use binary search for logarithmic runtime. I have an algorithm in C-esque psuedocode, but it has 3 base cases. Can these 3 base cases be condensed into 1 for a more elegant solution?

int function indexOfClosestLesser(array, searchValue, startIndex, endIndex) {
  if (startIndex == endIndex) {
    if (searchValue >= array[startIndex]) {
      return startIndex;
    } else {
      return -1;
    }
  }

  // In the simplistic case of searching for 2 in [0, 2], the midIndex
  // is always 0 due to int truncation. These checks are to avoid recursing
  // infinitely from index 0 to index 1. 
  if (startIndex == endIndex - 1) {
    if (searchValue >= array[endIndex]) {
      return endIndex;
    } else if (searchValue >= array[startIndex]) {
      return startIndex;
    } else {
      return -1;
    }
  }

  // In normal binary search, this would be the only base case
  if (startIndex < endIndex) {
    return -1;
  }

  int midIndex = endIndex / 2 + startIndex / 2;
  int midValue = array[midIndex];

  if (midValue > searchValue) {
    return indexOfClosestLesser(array, searchValue, startIndex, midIndex - 1);
  } else if (searchValue >= midValue) {
    // Unlike normal binary search, we don't start on midIndex + 1.
    // We're not sure whether the midValue can be excluded yet
    return indexOfClosestLesser(array, searchValue, midIndex, endIndex);
  }
}

9 Answers 9

10

Based on your recursive approach, I would suggest the following c++ snippet that reduces the number of different cases a bit:

int search(int *array, int start_idx, int end_idx, int search_val) {

   if( start_idx == end_idx )
      return array[start_idx] <= search_val ? start_idx : -1;

   int mid_idx = start_idx + (end_idx - start_idx) / 2;

   if( search_val < array[mid_idx] )
      return search( array, start_idx, mid_idx, search_val );

   int ret = search( array, mid_idx+1, end_idx, search_val );
   return ret == -1 ? mid_idx : ret;
}

Basically it performs a normal binary search. It only differs in the return statement of the last case to fulfill the additional requirement.

Here is a short test program:

#include <iostream>

int main( int argc, char **argv ) {

   int array[3] = { 10, 20, 30 };

   std::cout << search( array, 0, 2, 9 ) << std::endl;
   std::cout << search( array, 0, 2, 10 ) << std::endl;
   std::cout << search( array, 0, 2, 28 ) << std::endl;
   std::cout << search( array, 0, 2, 55555 ) << std::endl;

   return 0;
}

The output is as desired:

-1
 0
 1
 2
2
  • Let's say you're searching for 20 in [10, 20, 30]. In your first iteration, start_idx = 0, end_idx = 2, mid_idx = 1. Since the search value of 20 is not less than the middle value of 20, you will recurse on indices (1 + 1 = 2) to 2. At this point, you're already wrong because the possible values do not lay between start_idx of 2 to end_idx of also 2. The correct answer is index 1 because the search value of 20 is closest but not less than the number at index 1.
    – JoJo
    Mar 22, 2015 at 19:50
  • 3
    @JoJo That's why I check the return value of the recursion. If it returns -1 the previous value (1) is retained. You can try the code. It results in 1 for a search value of 20.
    – user0815
    Mar 22, 2015 at 20:31
4

Frankly speaking, I find the logic of finding a number greater than a given number a lot easier than the logic needed to find numbers less than or equal to a given number. Obviously, the reason behind that is the extra logic (that forms the edge cases) required to handle the duplicate numbers (of given num) present in the array.

public int justGreater(int[] arr, int val, int s, int e){
    // Returns the index of first element greater than val. 
    // If no such value is present, returns the size of the array.
    if (s >= e){
        return arr[s] <= N ? s+1 : s;
    }
    int mid = (s + e) >> 1;
    if (arr[mid] < val) return justGreater(arr, val, mid+1, e);
    return justGreater(arr, val, s, mid);
} 

and then to find the index of the closest value that is lesser than or equal to the search value in a sorted array, just subtract the returned value by 1:

ans = justGreater(arr, val, 0, arr.length-1) - 1;
4

Trick

The trick here is to search for searchValue + 1 and return the the found index as index - 1 which is left - 1 in the code below

For example if we search for 9 in [10, 20, 30]. The code will look for 10 and return that it's present at 0th index and we return 0-1 which is -1

Similarly if we try to search for 10 in the above example it will search for 10 + 1 and return 1st index and we return 1-1 which is 0

Code

def binary_search(array, searchValue, startIndex=0, endIndex=2 ** 32):
    """
    Binary search for the closest value less than or equal to the search value
    :param array: The given sorted list
    :param searchValue: Value to be found in the array
    :param startIndex: Initialized with 0
    :param endIndex: Initialized with 2**32
    :return: Returns the index closest value less than or equal to the search value
    """
    left = max(0, startIndex)
    right = min(len(array), endIndex)

    while left < right:
        mid = (left + right) // 2

        if array[mid] < searchValue + 1:
            left = mid + 1
        else:
            right = mid

    return left - 1

It can also be done in a single line with the standard library.

import bisect
def standard_binary_search(array, searchVal):
    return bisect.bisect_left(array, searchVal + 1) - 1

Testing

Testing the test cases provided by OP

array = [10, 20, 30]
print(binary_search(array, 9))
print(binary_search(array, 10))
print(binary_search(array, 28))
print(binary_search(array, 5555))

Results

-1
 0
 1
 2

I created a linear search to test the binary search.

def linear_search(array, searchVal):
    ans = -1
    for i, num in enumerate(array):
        if num > searchVal:
            return ans
        ans = i
    return ans

And a function to test all the binary search functions above. Check for correctness

def check_correctness(array, searchVal):
    assert binary_search(array, searchVal) == linear_search(array, searchVal)
    assert binary_search(array, searchVal) == standard_binary_search(array, searchVal)
    return binary_search(array, searchVal)

Driver Function

nums = sorted(
    [460, 4557, 1872, 2698, 4411, 1730, 3870, 4941, 77, 7789, 8553, 6011, 9882, 9597, 8060, 1518, 8210, 380, 6822, 9022,
     8255, 8977, 2492, 5918, 3710, 4253, 8386, 9660, 2933, 7880, 615, 1439, 9311, 3526, 5674, 1899, 1544, 235, 3369,
     519, 8018, 8489, 3093, 2547, 4903, 1836, 2447, 570, 7666, 796, 7149, 9623, 681, 1869, 4381, 2711, 9882, 4348, 4617,
     7852, 5897, 4135, 9471, 4202, 6630, 3037, 9694, 9693, 7779, 3041, 3160, 4911, 8022, 7909, 297, 7258, 4379, 3216,
     9474, 8876, 6108, 7814, 9484, 2868, 882, 4206, 3986, 3038, 3659, 3287, 2152, 2964, 7057, 7122, 261, 2716, 4845,
     3709, 3562, 1928]
)

for num in range(10002):
    ans = check_correctness(nums, num)
    if ans != -1:
        print(num, nums[check_correctness(nums, num)])

The driver function ran without any assert errors. This proves the correctness of the above two functions.

0
1

Commented version in typescript. Based on this answer but modified to return less than or equal to.

/**
 * Binary Search of a sorted array but returns the closest smaller value if the
 * needle is not in the array.
 *
 * Returns null if the needle is not in the array and no smaller value is in
 * the array.
 *
 * @param haystack the sorted array to search @param needle the need to search
 * for in the haystack @param compareFn classical comparison function, return
 * -1 if a is less than b, 0 if a is equal to b, and 1 if a is greater than b
 */
export function lessThanOrEqualBinarySearch<T>(
  haystack: T[],
  needle: T,
  compareFn: (a: T, b: T) => number
): T | null {
  let lo = 0;
  let hi = haystack.length - 1;
  let lowestFound: T | null = null;

  // iteratively search halves of the array but when we search the larger
  // half keep track of the largest value in the smaller half
  while (lo <= hi) {
    let mid = (hi + lo) >> 1;
    let cmp = compareFn(needle, haystack[mid]);

    // needle is smaller than middle
    // search in the bottom half
    if (cmp < 0) {
      hi = mid - 1;
      continue;
    }

    // needle is larger than middle
    // search in the top half
    else if (cmp > 0) {
      lo = mid + 1;
      lowestFound = haystack[mid];
    } else if (cmp === 0) {
      return haystack[mid];
    }
  }
  return lowestFound;
}

0

Here's a PHP version, based on user0815's answer.

Adapted it to take a function, not just an array, and made it more efficient by avoiding evaluation of $mid_idx twice.

function binarySearchLessOrEqual($start_idx, $end_idx, $search_val, $valueFunction)
{
    //N.B. If the start index is bigger or equal to the end index, we've reached the end!
    if( $start_idx >= $end_idx )
    {
        return $valueFunction($end_idx) <= $search_val ? $end_idx : -1;
    }

    $mid_idx = intval($start_idx + ($end_idx - $start_idx) / 2);

    if ( $valueFunction($mid_idx) > $search_val )  //If the function is too big, we search in the bottom half
    {
        return binarySearchLessOrEqual( $start_idx, $mid_idx-1, $search_val, $valueFunction);
    }
    else //If the function returns less than OR equal, we search in the top half
    {
        $ret = binarySearchLessOrEqual($mid_idx+1, $end_idx, $search_val, $valueFunction);

        //If nothing is suitable, then $mid_idx was actually the best one!
        return $ret == -1 ? $mid_idx : $ret;
    }
}

Rather than taking an array, it takes a int-indexed function. You could easily adapt it to take an array instead, or simply use it as below:

function indexOfClosestLesser($array, $searchValue) 
{
    return binarySearchLessOrEqual(
        0, 
        count($array)-1, 
        $searchValue,
        function ($n) use ($array) 
        { 
            return $array[$n]; 
        }
    );
}

Tested:

$array = [ 10, 20, 30 ];
echo "0:  " . indexOfClosestLesser($array, 0)  . "<br>"; //-1
echo "5:  " . indexOfClosestLesser($array, 5)  . "<br>"; //-1
echo "10: " . indexOfClosestLesser($array, 10) . "<br>"; //0
echo "15: " . indexOfClosestLesser($array, 15) . "<br>"; //0
echo "20: " . indexOfClosestLesser($array, 20) . "<br>"; //1
echo "25: " . indexOfClosestLesser($array, 25) . "<br>"; //1
echo "30: " . indexOfClosestLesser($array, 30) . "<br>"; //2
echo "35: " . indexOfClosestLesser($array, 35) . "<br>"; //2
0

Try using a pair of global variables, then reference those variables inside the COMPARE function for bsearch

In RPGIV we can call c functions.

The compare function with global variables looks like this:

dcl-proc compInvHdr;
  dcl-pi compInvHdr int(10);
    elmPtr1   pointer value;
    elmPtr2   pointer value;
  end-pi;
  dcl-ds elm1            based(elmPtr1) likeds(invHdr_t);
  dcl-ds elm2            based(elmPtr2) likeds(elm1);
  dcl-s  low             int(10) inz(-1);
  dcl-s  high            int(10) inz(1);
  dcl-s  equal           int(10) inz(0);

  select;
  when elm1.rcd.RECORDNO < elm2.rcd.RECORDNO;
    lastHiPtr = elmPtr2;
    return low;
  when elm1.rcd.RECORDNO > elm2.rcd.RECORDNO;
    lastLoPtr = elmPtr2;
    return high;
  other;
    return equal;
  endsl;
end-proc;

Remember, that in bsearch the first element is the search key and the second element is the actual storage element in your array/memory, that is why the COMPARE procedure is using elmPtr2;

the call to bsearch looks like this:

// lastLoPtr and LastHiPtr are global variables
// basePtr points to the beginning of the array
lastLoPtr = basePtr;  
lastHiPtr = basePtr + ((numRec - 1) * sizRec));
searchKey = 'somevalue'; 
hitPtr = bsearch(%addr(searchkey)
                :basePtr
                :numRec
                :sizRec
                :%PADDR('COMPINVHDR'));
if hitPtr <> *null;
//? not found 
  hitPtr = lastLoPtr;             
else;
//? found
endif;

So if the key is not found then the hitPtr is set to the key of the closest match, effectively archiving a "Less than or Equal key".

If you want the opposite, the next greater key. Then use lastHiPtr to reference the first key greater than the search key.

Note: protect the global variables against race conditions (if applicable).

0

Wanted to provide a non-binary search way of doing this, in C#. The following finds the closest value to X, without being greater than X, but it can be equal to X. My function also does not need the list to be sorted. It is also theoretically faster than O(n), but only in the event that the exact target number is found, in which case it terminates early and returns the integer.

    public static int FindClosest(List<int> numbers, int target)
    {
        int current = 0;
        int difference = Int32.MaxValue;
        foreach(int integer in numbers)
        {
            if(integer == target)
            {
                return integer;
            }
            int diff = Math.Abs(target - integer);
            if(integer <= target && integer >= current && diff < difference)
            {
                current = integer;
                difference = diff;
            }
        }
        return current;
    }

I tested this with the following setup, and it appears to be working flawlessly:

            List<int> values = new List<int>() {1,24,32,6,14,9,11,22 };
            int target = 21;
            int closest = FindClosest(values,target);
            Console.WriteLine("Closest: " + closest);
0

7 years later, I hope to provide some intuition:

If search_val <= arr[mid], we know for the sure that the solution resides in the interval [lo, mid], inclusive. So, we set right=mid (we probably can set right=mid-1 if mid is not included). Note that if search_val < arr[mid], we in fact know that the solution resides in [lo, mid), mid not inclusive. This is because search_val won't fall back on mid and use mid as the closest value <= search value if it is less than arr[mid].

On the other hand, search_val >= arr[mid]. In this case, we know that the solution resides in [mid, hi]. In fact, even if search_val > arr[mid], the solution is still [mid, hi]. This means that we should set left = mid. HOWEVER, in binary search, left is usually always set to mid + 1 to avoid infinite loops. But this means, when the loops at left==right, it is possible we are 1 index over the solution. Thus, we do a check at the very end to return either the left or left-1, that you can see in the other solutions.

Practice Problem: Search a 2D Matrix

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

The smart solution to this problem is to treat the two-dimensional array as an one-dimensional one and use regular binary search. But I wrote a solution that first locates the correct row. The process of finding the correct row in this problem is basically the same as finding the closest value less than equal to the search value.

Additionally link on binary search: Useful Insights into Binary Search

-2

a non-recursive way using loop, I'm using this in javascript so I'll just post in javascript:

let left = 0
let right = array.length
let mid = 0

while (left < right) {
    mid = Math.floor((left + right) / 2)
    if (searchValue < array[mid]) {
        right = mid
    } else {
        left = mid + 1
    }
}

return left - 1

since general guideline tells us to look at the middle pointer, many fail to see that the actual answer is the left pointer's final value.

1
  • Your solution cause an infinite loop, please refactor it.
    – Rickless
    Jun 4, 2020 at 21:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.