Novel Searching Algorithm: Interval Reduction Search (IRS)

Novel Searching Algorithm: Interval Reduction Search (IRS)

This algorithm is a hybrid of binary search and jump search designed for sorted arrays. Instead of halving the search space like binary search, it dynamically reduces the interval size based on a ratio derived from the search value and the data distribution.

Key Idea

1. Start with an interval covering the entire array.
2. Reduce the interval dynamically based on an adaptive ratio.
3. Continue reducing until the value is found or the interval becomes too small.

Fortran Implementation of IRS

This implementation assumes a sorted integer array and searches for a target value using the Interval Reduction Search method.

      PROGRAM INTERVAL_REDUCTION_SEARCH
      IMPLICIT NONE
      INTEGER, PARAMETER :: N = 20
      INTEGER :: ARR(N), TARGET, INDEX, I
      LOGICAL :: FOUND

      ! Sample sorted array
      DATA ARR /1, 3, 7, 9, 12, 15, 18, 21, 25, 28, 31, 35, 40, 44, 50, 55, 60, 65, 70, 75/

      ! Input the target value
      PRINT *, 'Enter the target value to search:'
      READ *, TARGET

      ! Call the search function
      CALL IRS_SEARCH(ARR, N, TARGET, INDEX, FOUND)

      ! Display the result
      IF (FOUND) THEN
         PRINT *, 'Target found at index:', INDEX
      ELSE
         PRINT *, 'Target not found.'
      END IF

      END PROGRAM INTERVAL_REDUCTION_SEARCH

      !------------------- INTERVAL REDUCTION SEARCH FUNCTION -------------------
      SUBROUTINE IRS_SEARCH(ARR, N, TARGET, INDEX, FOUND)
      IMPLICIT NONE
      INTEGER, INTENT(IN) :: N, TARGET, ARR(N)
      INTEGER, INTENT(OUT) :: INDEX
      LOGICAL, INTENT(OUT) :: FOUND
      INTEGER :: LEFT, RIGHT, MID, STEP

      LEFT = 1
      RIGHT = N
      FOUND = .FALSE.

      DO WHILE (LEFT <= RIGHT)
         ! Dynamic interval reduction: estimate midpoint based on value
         IF (ARR(RIGHT) /= ARR(LEFT)) THEN
            STEP = (TARGET - ARR(LEFT)) * (RIGHT - LEFT) / (ARR(RIGHT) - ARR(LEFT))
            MID = LEFT + STEP
         ELSE
            MID = (LEFT + RIGHT) / 2
         END IF

         ! Ensure MID stays within bounds
         MID = MAX(LEFT, MIN(MID, RIGHT))

         IF (ARR(MID) == TARGET) THEN
            INDEX = MID
            FOUND = .TRUE.
            RETURN
         ELSE IF (ARR(MID) < TARGET) THEN
            LEFT = MID + 1
         ELSE
            RIGHT = MID - 1
         END IF
      END DO

      INDEX = -1
      END SUBROUTINE IRS_SEARCH
        

Explanation of IRS Algorithm

1. Dynamic Interval Reduction
2. Adaptive Searching
3. Efficiency

Example Usage

Enter the target value to search:
35
Target found at index: 12
        

This method is faster than binary search in structured datasets and provides better adaptability than jump search.