CODEBHAVYA • DATA STRUCTURES

🔍 Searching

Learn important searching techniques in C from basic linear search to interview-oriented advanced searching methods.

SEARCHING

📖 Introduction to Searching

Searching is the process of finding whether a particular value exists in a collection of data and, if it exists, determining its position.

The choice of searching algorithm depends mainly on whether the data is sorted, how uniformly the values are distributed, and whether the data structure supports random access.

Important: Always check the data requirement before selecting a searching algorithm. Binary Search, for example, requires sorted data.
01 • SEARCHING ALGORITHM

🔎 Linear Search

Check each element one by one until the target is found or the collection ends.

💡 Key Idea

Start from the first element and compare every element with the target. The first matching position is returned. If no element matches, report that the target is not present.

🧠 Example

For [12, 7, 25, 9, 18] and target 25,
compare 12 → 7 → 25.
The target is found at index 2.

🔹 Step-by-Step Algorithm

  1. Read the array and target value.
  2. Start from index 0.
  3. Compare the current element with the target.
  4. If equal, return the index.
  5. Otherwise move to the next element.
  6. If the array ends, report not found.
Interactive Algorithm Visualization
CodeBhavya logoCodeBhavya

🎬 Premium Linear Search Visualizer

Watch the search pointer move one element at a time until the target is found.

850 ms

📦 Live Search State

Ready
Press Next to begin.
Step 00%
✅ Search visualization completed.

📊 Live Statistics

No comparison yet.

🧠 Current Search State

Waiting to start.

🧾 Recent Actions

💻 C Program
#include <stdio.h>

int main() {
    int n, target, i, position = -1;

    scanf("%d", &n);

    int a[n];

    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);

    scanf("%d", &target);

    for (i = 0; i < n; i++) {
        if (a[i] == target) {
            position = i;
            break;
        }
    }

    if (position != -1)
        printf("Element found at index %d\n", position);
    else
        printf("Element not found\n");

    return 0;
}

Sample Input

5
12 7 25 9 18
25

Sample Output

Element found at index 2

Input explanation: First enter the number of elements, then the elements, followed by the target.

⚡ Complexity

Best: O(1) Target is the first element.
Average: O(n) On average about half the elements may be checked.
Worst: O(n) Target is last or absent, so every element is checked.

Space: O(1) because only a few variables are used apart from the input array.

Interview note: Linear Search works on both sorted and unsorted arrays.
02 • SEARCHING ALGORITHM

⚡ Binary Search

Repeatedly divide a sorted search range into two halves.

💡 Key Idea

Binary Search compares the target with the middle element. If the target is smaller, continue in the left half; if larger, continue in the right half. The process continues until the target is found or the range becomes empty.

🔁 Approaches

💡 Example

For [3, 7, 11, 18, 25, 31, 40], searching for 25
starts at the middle, eliminates the left or right half based on comparison,
and quickly reaches 25.

🔹 Iterative Algorithm

  1. Set low = 0 and high = n - 1.
  2. Calculate mid = low + (high - low) / 2.
  3. If a[mid] == target, return the position.
  4. If target is smaller, set high = mid - 1.
  5. Otherwise set low = mid + 1.
  6. Repeat while low <= high.
Interactive Algorithm Visualization
CodeBhavya logoCodeBhavya

🎬 Premium Iterative Binary Search Visualizer

See low, high and mid shrink the sorted search range after each comparison.

850 ms

📦 Live Search State

Ready
Press Next to begin.
Step 00%
✅ Search visualization completed.

📊 Live Statistics

No comparison yet.

🧠 Current Search State

Waiting to start.

🧾 Recent Actions

💻 C Program
#include <stdio.h>

int main() {
    int n, target, low, high, mid, position = -1;

    scanf("%d", &n);
    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    scanf("%d", &target);

    low = 0;
    high = n - 1;

    while (low <= high) {
        mid = low + (high - low) / 2;

        if (a[mid] == target) {
            position = mid;
            break;
        } else if (target < a[mid]) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    if (position != -1)
        printf("Element found at index %d\n", position);
    else
        printf("Element not found\n");

    return 0;
}

Sample Input

7
3 7 11 18 25 31 40
25

Sample Output

Element found at index 4

🔁 Recursive Binary Search

The recursive version uses the same divide-and-conquer idea. Instead of updating the search range inside a loop, it calls itself on the appropriate half.

  1. Check whether low > high. If so, return -1.
  2. Find the middle index.
  3. If the middle value is the target, return it.
  4. Search the left or right half recursively.
Interactive Algorithm Visualization
CodeBhavya logoCodeBhavya

🎬 Premium Recursive Binary Search Visualizer

Follow each recursive call, active range and midpoint at every depth.

850 ms

📦 Live Search State

Ready
Press Next to begin.
Step 00%
✅ Search visualization completed.

📊 Live Statistics

No comparison yet.

🧠 Current Search State

Waiting to start.

🧾 Recent Actions

💻 C Program
#include <stdio.h>

int binarySearch(int a[], int low, int high, int target) {
    if (low > high)
        return -1;

    int mid = low + (high - low) / 2;

    if (a[mid] == target)
        return mid;

    if (target < a[mid])
        return binarySearch(a, low, mid - 1, target);

    return binarySearch(a, mid + 1, high, target);
}

int main() {
    int n, target;
    scanf("%d", &n);

    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    scanf("%d", &target);

    int position = binarySearch(a, 0, n - 1, target);

    if (position != -1)
        printf("Element found at index %d\n", position);
    else
        printf("Element not found\n");

    return 0;
}

Sample Input

7
3 7 11 18 25 31 40
31

Sample Output

Element found at index 5

⚡ Complexity

Best: O(1) The first middle element is the target.
Average: O(log n) Each comparison removes roughly half the remaining elements.
Worst: O(log n) The search continues until the range becomes empty.

Space: Iterative = O(1); Recursive = O(log n) because of the call stack.

Critical condition: Binary Search requires the data to be sorted.
03 • SEARCHING ALGORITHM

🔄 Rotated Binary Search

Search efficiently in a sorted array that has been rotated around a pivot.

💡 Key Idea

At least one half of a rotated sorted array is always normally sorted. Identify the sorted half, determine whether the target lies inside it, and discard the appropriate half.

💡 Example

For [15, 18, 2, 3, 6, 12], the array was originally sorted but rotated.
The algorithm determines which half remains sorted at every step.

🔹 Step-by-Step Algorithm

  1. Set low and high.
  2. Find mid.
  3. If the middle element is the target, return mid.
  4. Check whether the left half is sorted.
  5. If the target belongs to the sorted half, search there; otherwise search the other half.
  6. Repeat until the range is empty.
Interactive Algorithm Visualization
CodeBhavya logoCodeBhavya

🎬 Premium Rotated Binary Search Visualizer

See which half is sorted and which half can be discarded.

850 ms

📦 Live Search State

Ready
Press Next to begin.
Step 00%
✅ Search visualization completed.

📊 Live Statistics

No comparison yet.

🧠 Current Search State

Waiting to start.

🧾 Recent Actions

💻 C Program
#include <stdio.h>

int searchRotated(int a[], int n, int target) {
    int low = 0, high = n - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (a[mid] == target)
            return mid;

        if (a[low] <= a[mid]) {
            if (a[low] <= target && target < a[mid])
                high = mid - 1;
            else
                low = mid + 1;
        } else {
            if (a[mid] < target && target <= a[high])
                low = mid + 1;
            else
                high = mid - 1;
        }
    }

    return -1;
}

int main() {
    int n, target;
    scanf("%d", &n);

    int a[n];
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    scanf("%d", &target);

    int pos = searchRotated(a, n, target);

    if (pos != -1)
        printf("Element found at index %d\n", pos);
    else
        printf("Element not found\n");

    return 0;
}

Sample Input

6
15 18 2 3 6 12
3

Sample Output

Element found at index 3

⚡ Complexity

Best: O(1) Target is at the first middle position checked.
Average: O(log n) With distinct values, a half is discarded at each step.
Worst: O(log n) For distinct values, the search range halves repeatedly.

Space: O(1) for the iterative implementation.

Interview note: Duplicate values can make the worst case O(n) because it may become impossible to determine which half is strictly sorted.
04 • SEARCHING ALGORITHM

⏩ Jump Search

Search a sorted array by jumping fixed-size blocks and then performing a linear scan.

💡 Key Idea

Jump approximately √n positions at a time. Once a block containing the target is identified, perform a linear search inside that block.

🔹 Algorithm

  1. Choose block size √n.
  2. Jump through the array until the current value is at least the target.
  3. Linearly search the identified block.
  4. Return the index if found; otherwise return -1.
Interactive Algorithm Visualization
CodeBhavya logoCodeBhavya

🎬 Premium Jump Search Visualizer

Watch fixed-size jumps locate a candidate block, then a linear scan finish the search.

850 ms

📦 Live Search State

Ready
Press Next to begin.
Step 00%
✅ Search visualization completed.

📊 Live Statistics

No comparison yet.

🧠 Current Search State

Waiting to start.

🧾 Recent Actions

💻 C Program
#include <stdio.h>

int jumpSearch(int a[], int n, int target) {
    int step = 1;
    while (step * step < n)
        step++;

    int prev = 0;
    int next = step;

    while (prev < n && a[(next < n ? next : n) - 1] < target) {
        prev = next;
        next += step;

        if (prev >= n)
            return -1;
    }

    while (prev < n && prev < next) {
        if (a[prev] == target)
            return prev;
        if (a[prev] > target)
            return -1;
        prev++;
    }

    return -1;
}

int main() {
    int n, target;
    scanf("%d", &n);

    int a[n];
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    scanf("%d", &target);

    int pos = jumpSearch(a, n, target);

    if (pos != -1)
        printf("Element found at index %d\n", pos);
    else
        printf("Element not found\n");

    return 0;
}

Sample Input

10
2 5 8 12 16 21 27 31 36 40
27

Sample Output

Element found at index 6

⚡ Complexity

Best: O(1) Target is encountered immediately.
Average: O(√n) About √n jumps plus a scan of one block.
Worst: O(√n) Maximum jump and block scan are proportional to √n.

Space: O(1).

05 • SEARCHING ALGORITHM

📍 Interpolation Search

Estimate the likely position of the target using the values at the boundaries.

💡 Key Idea

Unlike Binary Search, which always chooses the middle, Interpolation Search estimates a position. It works especially well when sorted values are approximately uniformly distributed.

🔹 Position Formula

pos = low + ((target - a[low]) × (high - low)) / (a[high] - a[low])

🔹 Algorithm

  1. Set low and high.
  2. Check that the target is within the boundary values.
  3. Estimate the position using the interpolation formula.
  4. Compare the estimated value with the target.
  5. Move low or high accordingly.
  6. Repeat until found or the range becomes invalid.
Interactive Algorithm Visualization
CodeBhavya logoCodeBhavya

🎬 Premium Interpolation Search Visualizer

See the estimated probe position move according to the target and boundary values.

850 ms

📦 Live Search State

Ready
Press Next to begin.
Step 00%
✅ Search visualization completed.

📊 Live Statistics

No comparison yet.

🧠 Current Search State

Waiting to start.

🧾 Recent Actions

💻 C Program
#include <stdio.h>

int interpolationSearch(int a[], int n, int target) {
    int low = 0, high = n - 1;

    while (low <= high && target >= a[low] && target <= a[high]) {

        if (a[high] == a[low]) {
            if (a[low] == target)
                return low;
            return -1;
        }

        int pos = low + (int)((long long)(target - a[low]) *
                              (high - low) /
                              (a[high] - a[low]));

        if (a[pos] == target)
            return pos;

        if (a[pos] < target)
            low = pos + 1;
        else
            high = pos - 1;
    }

    return -1;
}

int main() {
    int n, target;
    scanf("%d", &n);

    int a[n];
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    scanf("%d", &target);

    int pos = interpolationSearch(a, n, target);

    if (pos != -1)
        printf("Element found at index %d\n", pos);
    else
        printf("Element not found\n");

    return 0;
}

Sample Input

10
10 20 30 40 50 60 70 80 90 100
70

Sample Output

Element found at index 6

⚡ Complexity

Best: O(1) The estimated position directly contains the target.
Average: O(log log n) For uniformly distributed sorted data, the estimate is very accurate.
Worst: O(n) Poorly distributed values can make the estimates ineffective.

Space: O(1).

Condition: It requires sorted data and is most effective when values are uniformly distributed.
06 • SEARCHING ALGORITHM

🌀 Fibonacci Search

Use Fibonacci numbers to divide a sorted array into search ranges.

💡 Key Idea

Fibonacci Search divides the search range using Fibonacci numbers instead of using a direct midpoint. It requires sorted data and achieves logarithmic search time.

🔹 Algorithm

  1. Generate Fibonacci numbers until one is at least n.
  2. Use the Fibonacci values to choose a probe position.
  3. Compare the probe element with the target.
  4. Reduce the Fibonacci range toward the left or right.
  5. Continue until the target is found or the range is exhausted.
Interactive Algorithm Visualization
CodeBhavya logoCodeBhavya

🎬 Premium Fibonacci Search Visualizer

Follow Fibonacci offsets as they choose probe positions and reduce the remaining range.

850 ms

📦 Live Search State

Ready
Press Next to begin.
Step 00%
✅ Search visualization completed.

📊 Live Statistics

No comparison yet.

🧠 Current Search State

Waiting to start.

🧾 Recent Actions

💻 C Program
#include <stdio.h>

int fibonacciSearch(int a[], int n, int target) {
    int fib2 = 0;
    int fib1 = 1;
    int fib = fib1 + fib2;

    while (fib < n) {
        fib2 = fib1;
        fib1 = fib;
        fib = fib1 + fib2;
    }

    int offset = -1;

    while (fib > 1) {
        int i = offset + fib2;
        if (i >= n)
            i = n - 1;

        if (a[i] < target) {
            fib = fib1;
            fib1 = fib2;
            fib2 = fib - fib1;
            offset = i;
        }
        else if (a[i] > target) {
            fib = fib2;
            fib1 = fib1 - fib2;
            fib2 = fib - fib1;
        }
        else {
            return i;
        }
    }

    if (fib1 && offset + 1 < n && a[offset + 1] == target)
        return offset + 1;

    return -1;
}

int main() {
    int n, target;
    scanf("%d", &n);

    int a[n];
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    scanf("%d", &target);

    int pos = fibonacciSearch(a, n, target);

    if (pos != -1)
        printf("Element found at index %d\n", pos);
    else
        printf("Element not found\n");

    return 0;
}

Sample Input

10
10 20 30 40 50 60 70 80 90 100
80

Sample Output

Element found at index 7

⚡ Complexity

Best: O(1) Target is found at the first probe.
Average: O(log n) Fibonacci-based reductions shrink the search range rapidly.
Worst: O(log n) Only logarithmically many probes are needed.

Space: O(1).

07 • SEARCHING ALGORITHM

⛓️ Skip List Search

Search an ordered linked structure using multiple levels of forward links.

💡 Key Idea

A Skip List augments a sorted linked list with extra forward links. Higher levels skip over many nodes, allowing the search to move quickly and then drop down to lower levels near the target.

🔹 Search Algorithm

  1. Start from the highest available level.
  2. Move forward while the next node is smaller than the target.
  3. When moving further would pass the target, drop one level.
  4. Repeat until level 0.
  5. Check the next node for equality.
Interactive Algorithm Visualization
CodeBhavya logoCodeBhavya

🎬 Premium Skip List Search Visualizer

Move across higher levels first and drop down when the next jump would pass the target.

850 ms

📦 Live Search State

Ready
Press Next to begin.
Step 00%
✅ Search visualization completed.

📊 Live Statistics

No comparison yet.

🧠 Current Search State

Waiting to start.

🧾 Recent Actions

💻 C Program
#include <stdio.h>
#include <stdlib.h>

#define MAX_LEVEL 3

typedef struct Node {
    int key;
    struct Node *forward[MAX_LEVEL + 1];
} Node;

Node *createNode(int key) {
    Node *node = (Node *)malloc(sizeof(Node));
    node->key = key;

    for (int i = 0; i <= MAX_LEVEL; i++)
        node->forward[i] = NULL;

    return node;
}

void insert(Node *head, int key, int level) {
    Node *update[MAX_LEVEL + 1];
    Node *current = head;

    for (int i = MAX_LEVEL; i >= 0; i--) {
        while (current->forward[i] != NULL &&
               current->forward[i]->key < key)
            current = current->forward[i];

        update[i] = current;
    }

    current = current->forward[0];

    if (current != NULL && current->key == key)
        return;

    Node *newNode = createNode(key);

    for (int i = 0; i <= level; i++) {
        newNode->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = newNode;
    }
}

int search(Node *head, int key) {
    Node *current = head;

    for (int i = MAX_LEVEL; i >= 0; i--) {
        while (current->forward[i] != NULL &&
               current->forward[i]->key < key)
            current = current->forward[i];
    }

    current = current->forward[0];

    if (current != NULL && current->key == key)
        return 1;

    return 0;
}

int main() {
    Node *head = createNode(-1);

    insert(head, 10, 0);
    insert(head, 20, 1);
    insert(head, 30, 2);
    insert(head, 40, 1);
    insert(head, 50, 3);
    insert(head, 60, 2);

    int target;
    scanf("%d", &target);

    if (search(head, target))
        printf("Element found\n");
    else
        printf("Element not found\n");

    return 0;
}

Sample Input

40

Sample Output

Element found

⚡ Complexity

Best: O(1) The target is found immediately after the starting point.
Average: O(log n) With balanced/random levels, multiple forward links skip many nodes.
Worst: O(n) If the structure becomes poorly balanced, the search can degrade to a linked-list scan.

Space: O(n) because extra forward pointers are stored.

Interview note: Skip Lists provide probabilistic alternatives to balanced search trees and are especially useful when ordered operations are required.
QUICK REVISION

📊 Searching Algorithm Comparison

Compare the major searching algorithms at a glance.

Algorithm Data Requirement Best Average Worst Space
Linear SearchSorted or UnsortedO(1)O(n)O(n)O(1)
Binary SearchSortedO(1)O(log n)O(log n)O(1)*
Recursive Binary SearchSortedO(1)O(log n)O(log n)O(log n)
Rotated Binary SearchRotated Sorted ArrayO(1)O(log n)O(log n)O(1)
Jump SearchSortedO(1)O(√n)O(√n)O(1)
Interpolation SearchSorted & Uniformly DistributedO(1)O(log log n)O(n)O(1)
Fibonacci SearchSortedO(1)O(log n)O(log n)O(1)
Skip List SearchSkip ListO(1)O(log n)O(n)O(n)

* Iterative Binary Search uses O(1) auxiliary space; recursive implementation uses O(log n) stack space.

Quick Interview Rule: Unsorted data → Linear Search | Sorted data → Binary Search | Rotated sorted array → Rotated Binary Search | Sorted uniformly distributed data → Interpolation Search | Ordered linked structure → Skip List.
INTERVIEW PREPARATION

📝 Important Interview Points

Key facts to remember before solving searching problems.

  • Binary Search requires sorted data.
  • Use low + (high - low) / 2 to calculate the midpoint safely.
  • Linear Search works on unsorted data.
  • Binary Search reduces the search space by approximately half each step.
  • Recursive Binary Search has O(log n) auxiliary stack space.
  • Rotated Binary Search identifies a sorted half at every step.
  • Interpolation Search is excellent for uniformly distributed sorted values.
  • Jump Search uses √n-sized blocks.
  • Fibonacci Search uses Fibonacci numbers to partition the search area.
  • Skip Lists use multiple levels of links to speed up ordered searches.
  • Always ask whether duplicate values are possible.
  • For duplicate arrays, interviewers may ask for first occurrence, last occurrence, or count of occurrences.
INTERVIEW TIPS

💡 Interview Tips

  1. First identify whether the input is sorted.
  2. Look for words such as "minimum", "maximum", "first", "last", or "closest"; they often indicate a Binary Search variation.
  3. Always define the search range clearly.
  4. Check boundary cases: empty array, one element, target at beginning, target at end, and target absent.
  5. For rotated arrays, determine which half is sorted before deciding where to move.
  6. Explain why the complexity is logarithmic instead of simply stating O(log n).
COMMON QUESTIONS

❓ Common Interview Questions

Think about each question first. If you are unsure, open the answer and learn the short interview-ready explanation.

1. Why must Binary Search use sorted data?

Binary Search decides whether to continue in the left half or right half by comparing the target with the middle element. That decision is valid only when the values are ordered.

Interview answer: Binary Search requires sorted data because the ordering allows every comparison to safely eliminate half of the remaining search space.
2. Why is Binary Search O(log n)?

After each comparison, Binary Search keeps only about half of the current elements. So the search sizes become n → n/2 → n/4 → ... → 1.

Interview answer: Binary Search is O(log n) because each comparison halves the remaining search range.
3. What is the difference between iterative and recursive Binary Search?

The iterative version repeatedly updates low and high inside a loop. The recursive version calls itself with a smaller range. Both take O(log n) search time, but recursion additionally uses call-stack space.

Interview answer: Iterative Binary Search uses a loop and O(1) auxiliary space; recursive Binary Search uses recursive calls and O(log n) stack space.
4. How do you avoid integer overflow while calculating mid?

Instead of mid = (low + high) / 2, use mid = low + (high - low) / 2. This avoids directly adding two potentially large indices.

Interview answer: Use low + (high - low) / 2 so low + high does not overflow.
5. How do you search a rotated sorted array?

Find mid. At least one side of a rotated sorted array is normally sorted. Identify that sorted half, check whether the target lies inside it, and discard the other half.

Interview answer: At every step, identify the sorted half and use the target range to decide which half to keep.
6. When is Interpolation Search better than Binary Search?

Interpolation Search is most effective when the array is sorted and values are distributed approximately uniformly. Its estimated position can then land very close to the target.

Interview answer: It can outperform Binary Search on large, sorted, uniformly distributed numeric data.
7. Why can Interpolation Search become O(n)?

If values are distributed very unevenly, the interpolation formula may repeatedly estimate poor positions and reduce the search range only a little at a time.

Interview answer: On non-uniform data, poor position estimates can make Interpolation Search degrade to linear-time behavior.
8. What is the block size used in Jump Search?

The usual block size is approximately √n. Jumping by about √n balances the number of jumps with the number of elements that may need to be scanned inside the final block.

Interview answer: Jump Search normally uses a block size of √n, giving O(√n) search time.
9. What is a Skip List?

A Skip List is a sorted linked structure with multiple levels of forward pointers. Higher levels skip over several nodes so the search can move quickly, then drop to lower levels near the target.

Interview answer: A Skip List is a probabilistic ordered structure that adds multiple forward-link levels to speed up searching.
10. How do duplicate values affect Rotated Binary Search?

With distinct values, it is normally easy to identify which half is sorted. With many duplicates, values at low, mid, and high may be equal, so the algorithm may not know which side can safely be discarded.

Interview answer: Duplicates can make the sorted half ambiguous and may degrade Rotated Binary Search from O(log n) to O(n).
PRACTICE

🎯 20 Searching Practice Problems

Try each problem yourself first. Use 💻 Solve It Yourself to write and test your C program. Use Hint only when needed, and Show Program if you want to study the complete solution.

📈 Searching Practice Progress
Solved0 / 20
Completed with Solution0
Total Score0 / 2000
Completion0%
A problem counts as Solved when all tests pass without opening the full solution. Problems completed after viewing the solution are tracked separately.
1. Find an element using Linear Search

Given an array and a target, print its index or -1.

Input: n, n integers, target

Output: index or -1

Scan from index 0 to n-1 and stop when the target is found.
💻 Solve It Yourself — Linear Search

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    int n, t, pos = -1;

    scanf("%d", &n);

    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    scanf("%d", &t);

    for (int i = 0; i < n; i++) {
        if (a[i] == t) {
            pos = i;
            break;
        }
    }

    printf("%d\n", pos);
    return 0;
}

Sample Input

5
4 8 2 9 6
9

Sample Output

3
2. Count occurrences of a target

Count how many times a value occurs in an array.

Input: n, array, target

Output: count

Increment a counter every time a[i] equals target.
💻 Solve It Yourself — Count occurrences of a target

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    int n, t, c = 0;

    scanf("%d", &n);

    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    scanf("%d", &t);

    for (int i = 0; i < n; i++)
        if (a[i] == t)
            c++;

    printf("%d\n", c);
    return 0;
}

Sample Input

7
2 4 2 7 2 8 2
2

Sample Output

4
3. Find first occurrence

Find the first index of a target.

Input: n, array, target

Output: first index or -1

Scan from left to right and stop at the first match.
💻 Solve It Yourself — Find first occurrence

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    int n, t, pos = -1;

    scanf("%d", &n);

    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    scanf("%d", &t);

    for (int i = 0; i < n; i++) {
        if (a[i] == t) {
            pos = i;
            break;
        }
    }

    printf("%d\n", pos);
    return 0;
}

Sample Input

6
5 3 8 3 9 3
3

Sample Output

1
4. Find last occurrence

Find the last index of a target.

Input: n, array, target

Output: last index or -1

Do not stop at the first match. Update the position every time the target is found.
💻 Solve It Yourself — Find last occurrence

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    int n, t, pos = -1;

    scanf("%d", &n);

    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    scanf("%d", &t);

    for (int i = 0; i < n; i++)
        if (a[i] == t)
            pos = i;

    printf("%d\n", pos);
    return 0;
}

Sample Input

6
5 3 8 3 9 3
3

Sample Output

5
5. Binary Search — iterative

Search for a target in a sorted array using iteration.

Input: sorted array and target

Output: index or -1

Maintain low and high and compare the target with the middle element.
💻 Solve It Yourself — Binary Search — iterative

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    int n, t, lo, hi, mid, pos = -1;

    scanf("%d", &n);

    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    scanf("%d", &t);

    lo = 0;
    hi = n - 1;

    while (lo <= hi) {
        mid = lo + (hi - lo) / 2;

        if (a[mid] == t) {
            pos = mid;
            break;
        }

        if (a[mid] < t)
            lo = mid + 1;
        else
            hi = mid - 1;
    }

    printf("%d\n", pos);
    return 0;
}

Sample Input

5
10 20 30 40 50
40

Sample Output

3
6. Binary Search — recursive

Implement Binary Search using recursion.

Input: sorted array and target

Output: index or -1

Create a recursive function with low and high parameters.
💻 Solve It Yourself — Binary Search — recursive

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int bs(int a[], int l, int h, int t) {
    if (l > h)
        return -1;

    int m = l + (h - l) / 2;

    if (a[m] == t)
        return m;

    if (t < a[m])
        return bs(a, l, m - 1, t);

    return bs(a, m + 1, h, t);
}

int main() {
    int n, t;

    scanf("%d", &n);

    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    scanf("%d", &t);

    printf("%d\n", bs(a, 0, n - 1, t));
    return 0;
}

Sample Input

6
2 5 8 11 14 19
14

Sample Output

4
7. First occurrence in sorted array

Find the first occurrence of a duplicate target using Binary Search.

Input: sorted array and target

Output: first index

When target is found, store mid and continue searching the left half.
💻 Solve It Yourself — First occurrence in sorted array

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    int n, t, l = 0, h, pos = -1;

    scanf("%d", &n);

    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    scanf("%d", &t);

    h = n - 1;

    while (l <= h) {
        int m = l + (h - l) / 2;

        if (a[m] == t) {
            pos = m;
            h = m - 1;
        } else if (a[m] < t) {
            l = m + 1;
        } else {
            h = m - 1;
        }
    }

    printf("%d\n", pos);
    return 0;
}

Sample Input

7
2 4 4 4 7 9 12
4

Sample Output

1
8. Last occurrence in sorted array

Find the last occurrence of a target using Binary Search.

Input: sorted array and target

Output: last index

When target is found, store mid and continue searching the right half.
💻 Solve It Yourself — Last occurrence in sorted array

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    int n, t, l = 0, h, pos = -1;

    scanf("%d", &n);

    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    scanf("%d", &t);

    h = n - 1;

    while (l <= h) {
        int m = l + (h - l) / 2;

        if (a[m] == t) {
            pos = m;
            l = m + 1;
        } else if (a[m] < t) {
            l = m + 1;
        } else {
            h = m - 1;
        }
    }

    printf("%d\n", pos);
    return 0;
}

Sample Input

7
2 4 4 4 7 9 12
4

Sample Output

3
9. Count occurrences in sorted array

Find how many times a target occurs.

Input: sorted array and target

Output: count

Find first and last occurrence; count = last - first + 1.
💻 Solve It Yourself — Count occurrences in sorted array

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int first(int a[], int n, int t) {
    int l = 0, h = n - 1, p = -1;

    while (l <= h) {
        int m = l + (h - l) / 2;

        if (a[m] == t) {
            p = m;
            h = m - 1;
        } else if (a[m] < t) {
            l = m + 1;
        } else {
            h = m - 1;
        }
    }

    return p;
}

int last(int a[], int n, int t) {
    int l = 0, h = n - 1, p = -1;

    while (l <= h) {
        int m = l + (h - l) / 2;

        if (a[m] == t) {
            p = m;
            l = m + 1;
        } else if (a[m] < t) {
            l = m + 1;
        } else {
            h = m - 1;
        }
    }

    return p;
}

int main() {
    int n, t;

    scanf("%d", &n);

    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    scanf("%d", &t);

    int f = first(a, n, t), l = last(a, n, t);

    printf("%d\n", f == -1 ? 0 : l - f + 1);
    return 0;
}

Sample Input

8
1 2 2 2 3 4 4 7
2

Sample Output

3
10. Search in rotated sorted array

Search a target in a rotated sorted array.

Input: rotated sorted array and target

Output: index or -1

At every step, identify which half is sorted.
💻 Solve It Yourself — Search in rotated sorted array

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    int n, t, l = 0, h, pos = -1;

    scanf("%d", &n);

    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    scanf("%d", &t);

    h = n - 1;

    while (l <= h) {
        int m = l + (h - l) / 2;

        if (a[m] == t) {
            pos = m;
            break;
        }

        if (a[l] <= a[m]) {
            if (a[l] <= t && t < a[m])
                h = m - 1;
            else
                l = m + 1;
        } else {
            if (a[m] < t && t <= a[h])
                l = m + 1;
            else
                h = m - 1;
        }
    }

    printf("%d\n", pos);
    return 0;
}

Sample Input

7
8 9 10 2 3 5 6
5

Sample Output

5
11. Jump Search

Search a sorted array using Jump Search.

Input: sorted array and target

Output: index or -1

Jump √n positions until you cross the target, then linearly scan that block.
💻 Solve It Yourself — Jump Search

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    int n, t, step = 1, prev = 0, pos = -1;

    scanf("%d", &n);

    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    scanf("%d", &t);

    while (step * step < n)
        step++;

    int next = step;

    while (prev < n && a[(next < n ? next : n) - 1] < t) {
        prev = next;
        next += step;

        if (prev >= n)
            break;
    }

    while (prev < n && prev < next) {
        if (a[prev] == t) {
            pos = prev;
            break;
        }

        if (a[prev] > t)
            break;

        prev++;
    }

    printf("%d\n", pos);
    return 0;
}

Sample Input

9
1 4 7 10 13 16 19 22 25
19

Sample Output

6
12. Interpolation Search

Search uniformly distributed sorted data using interpolation.

Input: sorted array and target

Output: index or -1

Estimate the position using the values at low and high.
💻 Solve It Yourself — Interpolation Search

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    int n, t, l = 0, h, pos = -1;

    scanf("%d", &n);

    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    scanf("%d", &t);

    h = n - 1;

    while (l <= h && t >= a[l] && t <= a[h]) {
        if (a[l] == a[h]) {
            if (a[l] == t)
                pos = l;
            break;
        }

        int p = l + (int)((long long)(t - a[l]) * (h - l) / (a[h] - a[l]));

        if (a[p] == t) {
            pos = p;
            break;
        }

        if (a[p] < t)
            l = p + 1;
        else
            h = p - 1;
    }

    printf("%d\n", pos);
    return 0;
}

Sample Input

10
10 20 30 40 50 60 70 80 90 100
90

Sample Output

8
13. Fibonacci Search

Search a sorted array using Fibonacci partitions.

Input: sorted array and target

Output: index or -1

Generate Fibonacci numbers until the largest one is at least n, then use the Fibonacci offsets to probe.
💻 Solve It Yourself — Fibonacci Search

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    int n, t;

    scanf("%d", &n);

    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    scanf("%d", &t);

    int f2 = 0, f1 = 1, f = f1 + f2;

    while (f < n) {
        f2 = f1;
        f1 = f;
        f = f1 + f2;
    }

    int off = -1, pos = -1;

    while (f > 1) {
        int i = off + f2;

        if (i >= n)
            i = n - 1;

        if (a[i] < t) {
            f = f1;
            f1 = f2;
            f2 = f - f1;
            off = i;
        } else if (a[i] > t) {
            f = f2;
            f1 = f1 - f2;
            f2 = f - f1;
        } else {
            pos = i;
            break;
        }
    }

    if (pos == -1 && f1 && off + 1 < n && a[off + 1] == t)
        pos = off + 1;

    printf("%d\n", pos);
    return 0;
}

Sample Input

8
5 10 15 20 25 30 35 40
30

Sample Output

5
14. Lower Bound

Find the first index whose value is greater than or equal to the target.

Input: sorted array and target

Output: lower-bound index

If a[mid] is at least target, store mid and move left.
💻 Solve It Yourself — Lower Bound

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    int n, t, l = 0, h, pos;

    scanf("%d", &n);

    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    scanf("%d", &t);

    h = n;
    pos = n;

    while (l < h) {
        int m = l + (h - l) / 2;

        if (a[m] >= t) {
            pos = m;
            h = m;
        } else {
            l = m + 1;
        }
    }

    printf("%d\n", pos);
    return 0;
}

Sample Input

6
2 4 7 9 12 15
8

Sample Output

3
15. Upper Bound

Find the first index whose value is greater than the target.

Input: sorted array and target

Output: upper-bound index

If a[mid] is greater than target, store mid and move left; otherwise move right.
💻 Solve It Yourself — Upper Bound

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    int n, t, l = 0, h, pos;

    scanf("%d", &n);

    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    scanf("%d", &t);

    h = n;
    pos = n;

    while (l < h) {
        int m = l + (h - l) / 2;

        if (a[m] > t) {
            pos = m;
            h = m;
        } else {
            l = m + 1;
        }
    }

    printf("%d\n", pos);
    return 0;
}

Sample Input

6
2 4 7 9 12 15
9

Sample Output

4
16. Search insertion position

Find the position where a target should be inserted in sorted order.

Input: sorted array and target

Output: insertion index

The insertion position is the lower bound of the target.
💻 Solve It Yourself — Search insertion position

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    int n, t, l = 0, h;

    scanf("%d", &n);

    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    scanf("%d", &t);

    h = n;

    while (l < h) {
        int m = l + (h - l) / 2;

        if (a[m] < t)
            l = m + 1;
        else
            h = m;
    }

    printf("%d\n", l);
    return 0;
}

Sample Input

5
10 20 30 40 50
35

Sample Output

3
17. Find peak element

Find an index of an element that is not smaller than its neighbors.

Input: n and array

Output: peak index

Compare mid with mid+1. If a[mid] is smaller, move right; otherwise move left including mid.
💻 Solve It Yourself — Find peak element

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    int n;

    scanf("%d", &n);

    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    int l = 0, h = n - 1;

    while (l < h) {
        int m = l + (h - l) / 2;

        if (a[m] < a[m + 1])
            l = m + 1;
        else
            h = m;
    }

    printf("%d\n", l);
    return 0;
}

Sample Input

6
1 3 8 7 5 2

Sample Output

2
18. Integer square root using Binary Search

Find floor(√x) without using a square-root library.

Input: non-negative integer x

Output: floor square root

Binary-search the answer from 0 to x and keep the largest mid whose square is at most x.
💻 Solve It Yourself — Integer square root using Binary Search

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    long long x;

    scanf("%lld", &x);

    long long l = 0, h = x, ans = 0;

    while (l <= h) {
        long long m = l + (h - l) / 2;

        if (m == 0 || m <= x / m) {
            ans = m;
            l = m + 1;
        } else {
            h = m - 1;
        }
    }

    printf("%lld\n", ans);
    return 0;
}

Sample Input

50

Sample Output

7
19. Search in a nearly sorted array

Each element may be at its correct position or one position away. Find the target.

Input: nearly sorted array and target

Output: index or -1

Check mid, mid-1, and mid+1 before moving the search range.
💻 Solve It Yourself — Search in a nearly sorted array

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    int n, t;

    scanf("%d", &n);

    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    scanf("%d", &t);

    int l = 0, h = n - 1, pos = -1;

    while (l <= h) {
        int m = l + (h - l) / 2;

        if (a[m] == t) {
            pos = m;
            break;
        }

        if (m - 1 >= l && a[m - 1] == t) {
            pos = m - 1;
            break;
        }

        if (m + 1 <= h && a[m + 1] == t) {
            pos = m + 1;
            break;
        }

        if (t < a[m])
            h = m - 2;
        else
            l = m + 2;
    }

    printf("%d\n", pos);
    return 0;
}

Sample Input

6
10 20 30 25 40 50
25

Sample Output

3
20. Find minimum in rotated sorted array

Find the minimum element in a rotated sorted array.

Input: rotated sorted array

Output: minimum value

Compare a[mid] with a[high]. If a[mid] is greater, the minimum lies to the right; otherwise it lies at mid or to the left.
💻 Solve It Yourself — Find minimum in rotated sorted array

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    int n;

    scanf("%d", &n);

    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    int l = 0, h = n - 1;

    while (l < h) {
        int m = l + (h - l) / 2;

        if (a[m] > a[h])
            l = m + 1;
        else
            h = m;
    }

    printf("%d\n", a[l]);
    return 0;
}

Sample Input

7
15 18 2 3 6 12 13

Sample Output

2
← Previous Topic: Data Structures Overview Next Topic: Sorting →