Binary search in C locates a target in a sorted array by repeatedly discarding half of the remaining candidates. This iterative implementation uses an overflow-resistant midpoint formula and returns a zero-based index or -1 when the target is absent.

How does binary search in C work iteratively?

For binary search C code, the loop tracks the active range with low and high. It checks the middle element, then moves the appropriate bound inward. The update must use mid + 1 or mid – 1 so the already-checked midpoint is not examined again.

Complete program:

#include <stdio.h>

int binary_search(const 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[mid] < target) low = mid + 1;

else high = mid – 1;

}

return -1;

}

int main(void) {

int values[] = {3, 8, 12, 17, 21, 21, 34, 50};

int n = sizeof values / sizeof values[0];

int tests[] = {3, 50, 17, 21, 13};

size_t count = sizeof tests / sizeof tests[0];

for (size_t i = 0; i < count; i++) {

int index = binary_search(values, n, tests[i]);

printf(“target %d: %d\n”, tests[i], index);

}

return 0;

}

What do sorted input, bounds, and return values mean?

The array must be sorted in ascending order. Without sorted input or another ordering guarantee, binary search cannot decide which half to discard; sort the data first when necessary.

low is the first possible index, and high is the last possible index. The initial range is from 0 through n – 1. The midpoint is calculated as low + (high – low) / 2, rather than (low + high) / 2, reducing the risk of integer overflow for large indexes.

This function returns the matching zero-based index immediately. If no candidate remains, low > high and the function returns -1. With duplicate values, it may return any matching occurrence; it does not promise the first or last duplicate.

How do you trace and test found and absent targets?

Using the sample array, trace a found target of 34:

• low = 0, high = 7, mid = 3: value 17 is less than 34, so set low to 4.
• low = 4, high = 7, mid = 5: value 21 is less than 34, so set low to 6.
• low = 6, high = 7, mid = 6: value 34 matches, so return index 6.

For an absent target of 13:

• Midpoint 3 contains 17, so high becomes 2.
• Midpoint 1 contains 8, so low becomes 2.
• Midpoint 2 contains 12, so low becomes 3.
• Now low is 3 and high is 2, so the function returns -1.

The program tests the first element (3), last element (50), middle element (17), a duplicate (21), and an absent target (13). Expected results are indexes 0, 7, 3, 5, and -1 respectively for this implementation.

How does C binary search compare with recursion, and what is its complexity?

A recursive version makes the shrinking range explicit but adds function-call overhead. It uses the same midpoint calculation and return convention:

int binary_search_recursive(const 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 (a[mid] < target)

return binary_search_recursive(a, mid + 1, high, target);

return binary_search_recursive(a, low, mid – 1, target);

}

Call it with binary_search_recursive(values, 0, n – 1, target). Both iterative and recursive binary search run in O(log n) time because each comparison halves the remaining range. The iterative form uses O(1) extra space; recursion uses O(log n) stack space.

To learn how to calculate time complexity, describe how an algorithm’s work grows as the input size grows. Define the input, identify a basic operation, count how often it runs, and simplify the resulting expression only after establishing that count. This process produces Big O notation, the standard way to describe runtime complexity.

Time complexity analysis focuses on growth rather than the exact time on one machine. Constants, hardware differences, and small implementation details matter less than whether the work grows linearly, quadratically, logarithmically, or exponentially.

How to Calculate Time Complexity from Input Size and a Basic Operation

Start by naming the input size. Use n for the number of items in an array, the length of a string, or the number of nodes in a structure. Then choose a basic operation, such as a comparison, assignment, arithmetic operation, or array access. Count how many times that operation executes.

For one loop that examines every item, the count is proportional to n:

for each item in an array: compare the item with a target

The comparison runs n times, so the complexity is O(n). If the loop performs three constant-time operations per item, the count might be 3n, but Big O removes the constant and still gives O(n).

Do not infer complexity from the number of statements alone. A statement inside a loop may execute millions of times, while several statements outside the loop may execute only once. Count execution frequency instead.

How Do Sequential and Nested Loops Affect Runtime Complexity?

Sequential sections add their costs. If one loop takes O(n) and a later loop takes O(n), the total is O(n + n), which simplifies to O(n). More generally, add the expressions first, then remove constants and lower-order terms. O(n² + n) becomes O(n²) because the quadratic term dominates as n grows.

Nested loops usually multiply their costs. If an outer loop runs n times and an inner loop also runs n times for every outer iteration, the operation runs n × n times. The result is O(n²).

Different bounds change the product. An outer loop that runs n times with an inner loop that runs 10 times has cost 10n, or O(n). An inner loop that runs from 1 through the current outer index performs 1 + 2 + … + n operations, which equals n(n + 1)/2 and simplifies to O(n²).

When loop bounds depend on separate inputs, retain both variables. For example, comparing every item in an array of size n with every item in an array of size m costs O(nm), not automatically O(n²).

When Does a Loop Become Logarithmic?

A loop is logarithmic when each iteration reduces the remaining work by a constant factor. A counter that doubles, such as 1, 2, 4, 8, and so on, reaches n after about log₂(n) iterations. A counter that halves follows the same growth pattern:

while n is greater than 1: divide n by 2

Its complexity is O(log n). The logarithm’s base is omitted in Big O because changing the base only changes a constant factor.

A loop that increases its counter by one is different: 1, 2, 3, …, n requires O(n) iterations. If a logarithmic loop is placed inside a linear loop, multiply the costs to get O(n log n).

How Does Time Complexity Analysis Handle Recursion and Cases?

For recursion, write a recurrence that describes the work in one call and the smaller calls it creates. A recursive linear search that checks one item and then searches the remaining items has the worst-case recurrence:

T(n) = T(n − 1) + O(1)

Each call removes one item and adds constant work, so the calls total O(n). The base case stops when no items remain. By contrast, a recurrence such as T(n) = T(n/2) + O(1) has O(log n) complexity because the input is halved at every call.

State the case being analyzed when the algorithm can stop early. For a linear search, the best case is O(1) when the first item matches. The average case is O(n) when a match is equally likely at any position, because the expected scan covers about half the input. The worst case is O(n) when the match is last or absent. These cases differ because the input’s position or contents change how much work the algorithm performs.

This quicksort example uses the Lomuto partition scheme, with the last element as the pivot and 0-based inclusive bounds. It shows the exact quicksort pseudocode, a complete partition trace, and the recursive calls needed to sort an array in place.

At each call, partition places the pivot in its final position. Quicksort then processes the elements to its left and right. A range containing zero or one element is already sorted.

Quicksort Example: The Divide-and-Conquer Plan

For a range A[low..high], choose a pivot and rearrange the range so values on one side are less than or equal to it, while values on the other side are greater. The partition function returns the pivot’s final index, p.

The recursive calls use low..p-1 and p+1..high. The pivot is excluded from both calls because it is already in the correct position.

This implementation uses Lomuto consistently: the pivot is A[high], the scan index j runs from low through high-1, and i marks the next position for a value less than or equal to the pivot.

Quicksort Pseudocode with Lomuto Partition

Use inclusive, 0-based indices. The base condition low >= high stops recursion.

QUICKSORT(A, low, high)

1. If low < high, set p = PARTITION(A, low, high).
2. Call QUICKSORT(A, low, p – 1).
3. Call QUICKSORT(A, p + 1, high).

PARTITION(A, low, high)

1. Set pivot = A[high].
2. Set i = low.
3. For each j from low to high-1, if A[j] <= pivot, swap A[i] and A[j], then increase i by one.
4. Swap A[i] and A[high].
5. Return i.

After partitioning, every element before index i is less than or equal to the pivot, and every element between i+1 and high is greater. The returned index is therefore the boundary for the two recursive ranges.

Partition Trace: Array Changes and Recursive Bounds

Trace A = [9, 4, 7, 3, 10, 5] with QUICKSORT(A, 0, 5). Lomuto selects 5, the final element, as the pivot.

• j = 0: 9 is greater than 5, so no swap occurs. The array remains [9, 4, 7, 3, 10, 5].
• j = 1: 4 qualifies. Swap positions 0 and 1: [4, 9, 7, 3, 10, 5]. Now i = 1.
• j = 2: 7 is greater than 5, so the array is unchanged.
• j = 3: 3 qualifies. Swap positions 1 and 3: [4, 3, 7, 9, 10, 5]. Now i = 2.
• j = 4: 10 is greater than 5, so the array is unchanged.
• Final swap: Swap A[2] and A[5]: [4, 3, 5, 9, 10, 7]. Partition returns p = 2.

The next bounds are QUICKSORT(A, 0, 1) and QUICKSORT(A, 3, 5). The left call uses pivot 3, producing [3, 4, 5, 9, 10, 7] and p = 0; its subcalls are (0, -1) and (1, 1), both finished ranges.

The right call uses pivot 7, producing [3, 4, 5, 7, 10, 9] and p = 3. Its right range (4, 5) uses pivot 9, producing [3, 4, 5, 7, 9, 10] and p = 4. The remaining bounds, (3, 2), (4, 3), and (5, 5), meet the base condition.

Time, Space, and Pivot Choice in Quicksort

Each partition scans its current range once. With reasonably balanced splits, the recurrence is T(n) = 2T(n/2) + O(n), giving average or expected time of O(n log n). If the pivot is repeatedly the smallest or largest value, the recurrence becomes T(n) = T(n-1) + O(n), producing worst-case time of O(n²). A sorted array and a last-element pivot can create this worst case.

Lomuto rearranges the array in place, requiring O(1) auxiliary storage apart from the recursion stack. Stack space averages O(log n) with balanced splits and can reach O(n) in the worst case. Randomized pivots or median-of-three selection reduce imbalance; move the selected pivot to A[high] before applying the same Lomuto rules.

Sequential search scans a collection from left to right, comparing the target with one item at a time. It returns the index as soon as it finds a match. If it reaches the end without a match, it returns a not-found result such as -1.

The method is useful when a collection is small, unsorted, or stored in a structure that does not support fast random lookup. Its running time depends on how many items the scan must compare.

How Does Sequential Search Scan a Collection?

Linear search begins at index 0 and examines each item in its existing order. For every position, it performs one equality comparison between the current item and the target.

1. Start at the first item.
2. Compare the current item with the target.
3. If they match, stop and return the current index.
4. If they do not match, move to the next item.
5. If no items remain, return the not-found result.

The scan stops early when the target appears near the beginning. It must inspect more of the collection when the target appears later or is absent. A sequential search does not rearrange the collection, so the order remains unchanged.

Linear Search Example: Found and Not Found

Consider this list, where indexes begin at zero:

[14, 3, 27, 8, 19]

To find 8, linear search makes these comparisons:

1. Index 0: compare 14 with 8 — no match.
2. Index 1: compare 3 with 8 — no match.
3. Index 2: compare 27 with 8 — no match.
4. Index 3: compare 8 with 8 — match.

The search returns index 3 after four comparisons.

To find 25, the search compares 25 with 14, 3, 27, 8, and 19. None matches, so the search returns -1 after five comparisons. This is a not-found result because every item was checked.

If the target were 14, the first item would match immediately. That found case would require only one comparison.

Linear Search Pseudocode: Return an Index or Not Found

The following pseudocode returns the first matching index. It returns -1 when the target is missing, including when the collection is empty.

linearSearch(items, target)

1. For index from 0 through the last index in items:
2. Compare items[index] with target.
3. If they are equal, return index.
4. After the loop finishes, return -1.

Returning as soon as a match appears makes the result the first occurrence when duplicate values exist. For example, searching [5, 2, 5] for 5 returns index 0 rather than continuing to index 2.

What Is Linear Search Time Complexity?

Linear search time complexity describes how the number of comparisons grows with the collection size, represented by n.

• Best case: O(1). The target is the first item, so the algorithm performs one comparison.
• Average case: O(n). If a present target is equally likely to occur at any position, the scan makes an average of (n + 1) / 2 comparisons. This simplifies to O(n).
• Worst case: O(n). The target is the final item or is not present, so the algorithm checks all n items.

The exact comparison count follows the trace: position i requires i + 1 comparisons, while an absent target requires n. The algorithm uses O(1) auxiliary space because it stores only the current index and target-related variables; it does not create another collection.

Bogosort sorts by repeatedly randomizing a list until the list happens to be in ascending order. Its stopping condition is simple—stop when an ordered scan finds no inversion—but its expected work is impractical: for n distinct items, one successful permutation appears only once in n! equally likely permutations on average.

Bogobogosort is a separate recursive variant, not another spelling for bogosort. It adds nested sorting and retry stages, making its expected behavior even less practical.

How Bogosort Works: Stopping Condition, Pseudocode, and a Tiny Trace

Assume the input contains distinct values and should be sorted in ascending order. Bogosort tests the current order, then randomly shuffles the entire list when the test fails. It stops only after isSorted(A) returns true.

Pseudocode:

1. If isSorted(A) is true, return A.
2. Shuffle A uniformly at random.
3. Repeat steps 1 and 2 until the list is sorted.

For the tiny input [2, 1, 3], the first check fails because 2 precedes 1. A possible shuffle produces [1, 3, 2], which also fails. Another shuffle might produce [3, 2, 1], followed by [1, 2, 3]. The algorithm stops at that point. A random shuffle can repeat an earlier arrangement, so this trace is only one possible path.

Why Does Bogosort’s Expected Runtime Grow Factorially?

With n distinct values, there are n! possible permutations. Under a uniform shuffle, exactly one is sorted, giving each attempt a success probability of 1/n!. The geometric-distribution intuition is therefore straightforward: the expected number of attempts is n!.

That count grows quickly: five items have 120 possible orders, while ten items have 3,628,800. Each attempt also needs an order check, which takes O(n) time. Bogosort consequently has an expected running time commonly expressed as O(n · n!), assuming uniform shuffling and distinct elements.

Its randomized worst case has no finite upper bound. The shuffling process could, in principle, avoid the sorted permutation indefinitely, even though the probability of eventual success is one under standard independent randomization.

How Bogobogosort Differs: A Separate Recursive Variant

Classic bogobogosort uses recursion to make the retry process more deeply nested:

1. Recursively apply bogobogosort to the first n − 1 items.
2. When that prefix is sorted, check the entire list.
3. If the full list is not sorted, shuffle all n items and restart the process.

The one-item case is already sorted and serves as the base case. The defining difference is that an outer attempt can invoke a complete recursive attempt on a shorter prefix before it gets another chance to test the full list. Ordinary bogosort simply shuffles until the whole list is sorted; bogobogosort builds recursive retries into that loop.

Its expected complexity depends on the precise implementation and shuffle model. Informal analyses of the classic variant often describe growth on the order of O((n!)^n!), or otherwise use superfactorial-style estimates. The exact label matters less than the structure: its expected runtime is vastly worse than bogosort’s factorial behavior, and its randomized worst case is likewise unbounded.

Why Are These Algorithms Still Discussed?

Bogosort and bogobogosort are useful cautionary examples rather than practical sorting tools. They make probability concrete, show why factorial search spaces become unmanageable, and demonstrate how a recursive retry can amplify an already poor algorithm. They also help separate expected runtime from worst-case guarantees: a process can be almost certain to finish eventually while still requiring an absurd expected amount of work.

Big O graph comparisons show how an algorithm’s work grows as the input size, n, increases. The most useful order is O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), and O(n!). Curves that look similar at small inputs separate sharply at larger ones.

Big O describes growth, not exact wall-clock time. Hardware, implementation, constants, and input patterns affect measured time, while Big O helps compare how algorithms scale.

Big O graph: How growth rates diverge

This growth-rate chart orders common complexity classes from slowest-growing to fastest-growing:

1. O(1), constant: The work stays roughly the same regardless of n, such as reading an array item by index.
2. O(log n), logarithmic: Each step removes a fraction of the remaining input. Binary search is the standard example.
3. O(n), linear: Work increases in direct proportion to the input, such as scanning every item once.
4. O(n log n), linearithmic: Common in efficient comparison sorting, including merge sort and average-case quicksort.
5. O(n²), quadratic: Two input-sized loops can compare many pairs, as in basic comparison sorts.
6. O(2ⁿ), exponential: Each added input item can double the work, often appearing in exhaustive subset searches.
7. O(n!), factorial: Work grows by trying every permutation, making it impractical quickly.

Big O time complexity from constant to factorial

Concrete scale examples make the divergence easier to judge. At n = 1,000, a linear algorithm performs roughly 1,000 units of work, while a quadratic one can reach about 1,000,000. At n = 1,000,000, O(n) is about 1,000,000 units and O(n²) is about 1,000,000,000,000.

• O(1): About 1 operation remains about 1 operation at every input size.
• O(log n): Binary search needs about 20 halvings for 1,000,000 items because log₂(1,000,000) is close to 20.
• O(n log n): At 1,000,000 items, a rough comparison count is 1,000,000 × 20, before constants and lower-order work.
• O(2ⁿ): At n = 20, there are 1,048,576 possible branches; at 40, there are more than 1 trillion.
• O(n!): 10! equals 3,628,800 arrangements, while 13! exceeds 6 billion.

These are operation-count intuitions, not timing promises. A highly optimized O(n²) routine can beat an O(n log n) routine for a small input, but the growth-rate advantage usually dominates as n expands.

Big O cheat sheet for sorting algorithms

Use this Big O sorting reference to compare the usual best, average, and worst runtimes. Auxiliary space excludes the input array itself.

• Bubble sort: Best O(n) with early-exit detection; average O(n²); worst O(n²); auxiliary space O(1).
• Insertion sort: Best O(n) on an already sorted or nearly sorted list; average O(n²); worst O(n²); auxiliary space O(1).
• Selection sort: Best, average, and worst O(n²); auxiliary space O(1).
• Merge sort: Best, average, and worst O(n log n); auxiliary space O(n) for the usual array implementation.
• Quicksort: Best O(n log n); average O(n log n); worst O(n²) with poor pivot choices; auxiliary space averages O(log n) for the recursion stack and can reach O(n).
• Heap sort: Best, average, and worst O(n log n); auxiliary space O(1).
• Counting sort: Best, average, and worst O(n + k), where k is the value range; auxiliary space O(n + k).

How to read Big O runtime in best, average, and worst cases

Big O runtime labels describe how an algorithm behaves under a selected input condition. Best case is the most favorable arrangement, average case represents typical assumptions, and worst case is the slowest permitted arrangement.

For example, insertion sort is O(n) when data is already ordered because each item moves little, but O(n²) when data is reverse-ordered. Quicksort is usually O(n log n), yet an unfavorable pivot sequence can produce O(n²). Merge sort gives the most consistent comparison-sort bound—O(n log n) in all three cases—but uses extra memory. For nearly sorted, small inputs, insertion sort’s low overhead can be preferable; for predictable large-input performance, merge sort or heap sort offers a stronger worst-case guarantee.

The 3Sum task takes an array of integers and a target value, then returns every value triple whose three numbers add to that target. Each triple must be unique by value, so the same combination is returned once even when duplicate indices can form it.

The efficient approach sorts the array, fixes one number, and scans the remaining range with two pointers. It reduces the search from cubic time to O(n²), while duplicate skipping preserves the output contract.

What Does 3Sum Return?

Define the input, target, and output contract

Given an integer array nums and an integer target, return a list of triples [a, b, c] such that a + b + c = target. The order inside a triple is normally ascending, and the result can be empty when no combination qualifies.

Require value-unique triples, not index-unique matches

Uniqueness applies to values rather than positions. For example, an array containing several copies of -1 must not produce [-1, 0, 1] repeatedly merely because different copies occupy different indices. Sorting makes those repeated values adjacent, which makes them easy to skip.

Why Is the Three-Sum Problem Expensive to Brute Force?

Count the cubic search space

The direct solution tests every combination of three indices. With n values, that is roughly n × (n – 1) × (n – 2) / 6 checks, or O(n³) time. Each check adds three values and compares the sum with the target.

Use brute force as a correctness baseline

Brute force is useful for small inputs and test validation because its logic is straightforward. For production-sized arrays, the cubic growth becomes expensive. A set can remove duplicate outputs, but it does not eliminate the cost of examining nearly every triple.

How the 3Sum algorithm Uses Sorting and Two Pointers

Sort the array and fix one value

Sort nums in ascending order. For each index i, treat nums[i] as the first value, set left = i + 1, and set right to the final index. The remaining task is a two-sum search for target – nums[i].

Move pointers based on the current sum

• If the three-value sum is too small, increase left to make the sum larger.
• If the sum is too large, decrease right to make the sum smaller.
• If the sum matches, record the triple, then move both pointers inward.

Walk through [-4, -1, -1, 0, 1, 2] with target 0

Start with -4. The pointers begin at -1 and 2, producing -3, so move left rightward. The next sums are -3, -2, and -1; each is too small, so left continues forward until the scan ends.

Next, fix -1 at index 1. With the second -1 and 2, the sum is 0, so record [-1, -1, 2]. Move both pointers: 0 and 1 also produce 0, so record [-1, 0, 1]. The next pointer positions cross. The second -1 at index 2 is skipped because it repeats the fixed value. The final result contains those two triples.

Implement the sorted scan

1. Sort the input array.
2. Loop through each possible first index while at least two values remain.
3. Skip the current index when its value equals the previous fixed value.
4. Use left and right pointers, calculate the sum, and move the appropriate pointer.
5. After recording a match, advance past equal left values and retreat past equal right values.

How Does Duplicate Skipping Affect Complexity?

Skip repeated fixed values and pointer values

Before each scan, skip a fixed value that equals the value at the preceding index. After finding a match, move left past every identical value and move right past every identical value. This prevents duplicate triples without relying on a set.

Compare O(n²) time with sorting and extra-space costs

Sorting costs O(n log n). The outer loop and two-pointer scans cost O(n²), so the complete algorithm remains O(n²). An in-place sort uses O(1) auxiliary space apart from the output; copying the array first adds O(n) space. The returned triples require additional output space proportional to their number.