Jump Search on a Sorted Array

You are given an array of n distinct integers sorted in strictly increasing order, and a target value x. Implement the jump search technique: starting from index 0, skip ahead in fixed-size blocks of length floor(sqrt(n)) until you find a block whose last element is not smaller than x, then perform a linear scan backward through that block to locate x. Output the 0-based index of x if found, otherwise output -1.

Input: The first line contains the integer n. The second line contains n space-separated strictly increasing integers. The third line contains the integer target x. Output: Print a single integer: the 0-based index of x in the array, or -1 if x is not present.

1 <= n <= 10^5 Array elements are strictly increasing (all distinct) -10^9 <= a[i], x <= 10^9

The optimal block size of sqrt(n) is a specific, derivable value (from balancing jump count against scan length) - not an arbitrary choice, and being able to justify WHY sqrt(n) specifically minimizes worst-case work is a valuable detail to know.

Search a sorted array by jumping ahead in fixed-size blocks, then scanning backward within the block that could contain the target. Brute force: Use a plain linear scan through the WHOLE array - this costs O(n), more than necessary given the array's sorted structure. Optimised: Jumping in blocks of size sqrt(n) balances the cost of 'how many jumps' against 'how much to scan within a block' optimally - jumping too far would need a long backward scan, jumping too little would need too many jumps; sqrt(n) is exactly the block size that minimizes the WORST-CASE total work, giving O(sqrt(n)) instead of O(n) or the O(log n) that binary search would achieve (jump search being a middle ground, useful when backward-stepping is much cheaper than random access in the actual underlying storage medium).

1. Pick a block size of floor(sqrt(n)) and JUMP FORWARD in strides of that size, comparing the element at the end of each stride to the target. 2. Stop jumping as soon as a block's last element is >= the target - the target, if present, must be inside THAT block. 3. Finish with a plain LINEAR SCAN over just that block (not the whole array) to find the exact position.

Time: O(sqrt(n)) - both the number of jumps and the final linear scan within a block are bounded by sqrt(n). Space: O(1) - just a couple of index variables.

The target may be smaller than every element, larger than every element, or equal to the first/last element; n may be as small as 1.

Be ready to mention when jump search is preferred over binary search in PRACTICE - specifically for data structures where jumping BACKWARD is expensive or impossible (like certain sequential-access storage systems), where binary search's random jumps would be costly but jump search's forward-then-limited-backward pattern works better.