Jump Search, C# - rextester

Jump Search

//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rextester
{
    public class Program
    {
        public static void Main(string[] args)
        {
            // Jump Search
            // A jump search locates an item in a sorted array by jumping k itens and then verify if the item wanted is between the previous jump and current jump
            
            // Define the value of k, the number of jump: Optimal jump size is √N where the N is the length of array
            // Jump the array k-by-k searching by the condition Array[i] < valueWanted < Array[i+k] 
            // Do a linear search between Array[i] and Array[i + k]
            
            //Your code goes here
            Console.WriteLine("----------- Jump Search -------------");
               
            int[] nums = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20}; 
            int searchNum = 18; 
  
            int findIndx = jumpSearch(nums, searchNum); 
            if(findIndx >= 0 ) {
                Console.WriteLine("Number {0} found at index {1} and at Location {2}", searchNum, findIndx, findIndx + 1);
            }
            else {
                Console.WriteLine("NOT FOUND");
            }
      
        }
        
    public static int jumpSearch(int[] nums, int searchNum) 
    { 
        int count = nums.Length; 
  
        // Finding value jump step to be jumped 
        int step = (int)Math.Floor(Math.Sqrt(count)); 
        int jumpIndx = step;
  
        // Finding the block where element is present 
        int prev = 0; 
        while (nums[Math.Min(jumpIndx, count)-1] < searchNum) 
        { 
            prev = jumpIndx; 
            jumpIndx += step; 
            if (prev >= count) 
                return -1; 
        } 
  
        // linear search 
         for(int indx=prev; indx < Math.Min(jumpIndx, count); indx++){
                if(searchNum == nums[indx]){
                    return indx;
                }
            }
        
        return -1; 
    } 
        
        
    }
}


run \| edit \| history \| help	0