exponential search in bash

Posted on | by root

Exponential search is an algorithm designed to search for a target value in a sorted array. It is useful in scenarios when dealing with large or potentially infinite datasets and it can also help you find a number, which is not known in advance. Let’s see how it works and how to implement exponential search in bash.

How does it work

Exponential search consists of two steps:

1) Start by checking the first element. If it isn’t the target, double the index each time (e.g., 1, 2, 4, 8, etc.) until you either find the target or surpass the array’s size or a value larger than the target.

2) Once you’ve identified the potential range where the target might be, use binary search within that range to efficiently find the exact position of the target. It works by repeatedly dividing the search interval in half. Start by comparing the target with the middle element – if the target is smaller, narrow the search to the left half. If the target is larger, narrow the search to the right half.

Exponential search in action

Say we have remote resource https://binary.lt/exponential/?guess=1 which accepts number and returns HTTP 200, if number is “correct”. Otherwise, it will return HTTP 400. That number is ever increasing so we can not be certain, what is the last possible number at some given point of time. For the sake of simplicity, this number in our example will be simple UNIX timestamp.

<?php

  $guess=(int)$_GET['guess'];

  if ($guess > time()) {
    http_response_code(400);
    echo "Bad request";
    exit;
  }

  echo "OK";

?>

Implementing exponential search in bash

The two steps to be implemented are actually nothing too complex. It can easily be implemented in bash. Here is a code which will try to guess the last number in our external resource. It will rely on returned HTTP status code – last one which is still returning 200 is our target.

#!/bin/bash

# first part of iterations
# exponential search

last_guess=1
steps=0
result=200

echo "phase 1: starting exponential search"

while [[ ${result} -eq 200 ]]; do

  result=$(curl -o /dev/null -s -w "%{http_code}\n" https://binary.lt/exponential/?guess=${last_guess})

  echo "phase 1: ${last_guess}"

  [[ $result == 200 ]] && last_guess=$((last_guess*2))

  steps=$((steps+1))

done

# so it is now beteen ${last_guess} and ${last_guess} / 2

# second part of iterations
# binary search

echo "phase 2: starting binary search"

lower_limit=$((last_guess/2))
upper_limit=${last_guess}
middle_number=$(((lower_limit+upper_limit)/2))

while [[ ${lower_limit} -lt $((upper_limit-1)) ]]; do

  echo "phase 2: between ${lower_limit} and ${upper_limit} - now testing ${middle_number}"

  last_guess=${middle_number}

  result=$(curl -o /dev/null -s -w "%{http_code}\n" https://binary.lt/exponential/?guess=${last_guess})

  if [[ ${result} == 200 ]]; then
    lower_limit=${middle_number}
  else
    upper_limit=${middle_number}
  fi

  middle_number=$(((lower_limit+upper_limit)/2))

  steps=$((steps+1))

done

echo "result: ${last_guess} guessed in ${steps} steps"

exit 0

Testing the implementation

So now time to see exponential search in action. We will call the php script above trying to guess the correct number. And here is the result:

[root@linux ~]# ./exponential.sh
phase 1: starting exponential search
phase 1: 1
phase 1: 2
phase 1: 4
phase 1: 8
phase 1: 16
phase 1: 32
phase 1: 64
phase 1: 128
phase 1: 256
phase 1: 512
phase 1: 1024
phase 1: 2048
phase 1: 4096
phase 1: 8192
phase 1: 16384
phase 1: 32768
phase 1: 65536
phase 1: 131072
phase 1: 262144
phase 1: 524288
phase 1: 1048576
phase 1: 2097152
phase 1: 4194304
phase 1: 8388608
phase 1: 16777216
phase 1: 33554432
phase 1: 67108864
phase 1: 134217728
phase 1: 268435456
phase 1: 536870912
phase 1: 1073741824
phase 1: 2147483648
phase 2: starting binary search
phase 2: between 1073741824 and 2147483648 - now testing 1610612736
phase 2: between 1610612736 and 2147483648 - now testing 1879048192
phase 2: between 1610612736 and 1879048192 - now testing 1744830464
phase 2: between 1610612736 and 1744830464 - now testing 1677721600
phase 2: between 1677721600 and 1744830464 - now testing 1711276032
phase 2: between 1711276032 and 1744830464 - now testing 1728053248
phase 2: between 1711276032 and 1728053248 - now testing 1719664640
phase 2: between 1719664640 and 1728053248 - now testing 1723858944
phase 2: between 1723858944 and 1728053248 - now testing 1725956096
phase 2: between 1723858944 and 1725956096 - now testing 1724907520
phase 2: between 1724907520 and 1725956096 - now testing 1725431808
phase 2: between 1724907520 and 1725431808 - now testing 1725169664
phase 2: between 1724907520 and 1725169664 - now testing 1725038592
phase 2: between 1724907520 and 1725038592 - now testing 1724973056
phase 2: between 1724973056 and 1725038592 - now testing 1725005824
phase 2: between 1725005824 and 1725038592 - now testing 1725022208
phase 2: between 1725005824 and 1725022208 - now testing 1725014016
phase 2: between 1725005824 and 1725014016 - now testing 1725009920
phase 2: between 1725005824 and 1725009920 - now testing 1725007872
phase 2: between 1725005824 and 1725007872 - now testing 1725006848
phase 2: between 1725006848 and 1725007872 - now testing 1725007360
phase 2: between 1725006848 and 1725007360 - now testing 1725007104
phase 2: between 1725007104 and 1725007360 - now testing 1725007232
phase 2: between 1725007232 and 1725007360 - now testing 1725007296
phase 2: between 1725007296 and 1725007360 - now testing 1725007328
phase 2: between 1725007296 and 1725007328 - now testing 1725007312
phase 2: between 1725007312 and 1725007328 - now testing 1725007320
phase 2: between 1725007320 and 1725007328 - now testing 1725007324
phase 2: between 1725007320 and 1725007324 - now testing 1725007322
phase 2: between 1725007322 and 1725007324 - now testing 1725007323
result: 1725007323 guessed in 62 steps
[root@linux ~]#

Since the number that we obtain must be “current” UNIX timestamp, let’s verify if it is what we expect it to be:

[root@linux ~]# we_got=$(./exponential.sh | tail -1 | grep -Po "result: \K(\d+)") && echo -e "result was:\n$(date -d@${we_got} +"%Y-%m-%d %H:%M:%S")" && echo -e "now is:\n$(date +"%Y-%m-%d %H:%M:%S")"
result was:
2024-08-30 11:53:11
now is:
2024-08-30 11:53:11
[root@linux ~]#