Binary Search with Strings: Code, Sorting, and Complexity

Last Tuesday, a teammate posted a message in our channel with a typo in the title: "binary search withs strings not working." He had ported a perfectly fine integer binary search over to a sorted array of words, and it returned -1 for a name that was visibly sitting in the list. He had checked the array. He had checked the target. He had not checked the one thing that actually changes when you move from int[] to String[]: comparison.

Binary search with strings is the same halving algorithm you already know, on one condition: the list must be sorted lexicographically, and the comparison rule you use while searching must match the one you used while sorting. Once those two pieces are in place, everything else is mechanics. This tutorial walks through lexicographic ordering, the sort-first requirement, working implementations in Python, Java, and JavaScript, the hidden cost of string comparisons, and the edge cases that generate late-night debugging sessions.

<img src="/cdn-img/photos/5652116/pexels-photo-5652116.jpeg?auto=compress&cs=tinysrgb&h=650&w=940" alt="Close-up of "TARGET" spelled with Scrabble tiles on a white background. Conceptual and selective focus." width="940" height="650" />

Binary Search with Strings: The One Core Difference

How the Binary Search Pattern Works

Binary search narrows a problem by halves. You keep two pointers, low and high, that delimit the only region where the target can still be hiding. At each step, you look at the middle element, compare it against the target, and decide which half to discard.

Let me trace the classic pattern on a sorted word list:

sorted: ['apple', 'banana', 'cherry', 'date', 'fig']
searching for: 'date'

low = 0, high = 4
mid = 2  ->  arr[2] = 'cherry'
'date' > 'cherry'  ->  discard left half, low = 3

low = 3, high = 4
mid = 3  ->  arr[3] = 'date'
match  ->  return 3

The identical sequence would run for an integer array like [1, 3, 5, 7, 9] searching for 7. The loop, the pointer arithmetic, and the halving logic don't change. Only the comparison operation changes meaning. For numbers, you use numeric ordering. For strings, you use lexicographic ordering.

Lexicographic Order Defines Less Than and Greater Than

When a program compares two strings, it checks characters from left to right. The first position where the strings differ decides the result. 'apple' < 'banana' because 'a' < 'b'. 'banana' < 'cherry' because 'b' < 'c'. If every character matches but one string ends first, the shorter string is smaller: 'app' < 'apple'.

This rule is called lexicographic order, and programmers often describe it as "dictionary order." There is an important caveat, though. Python, Java, and JavaScript all compare strings by Unicode code point by default. That means all uppercase letters sort before all lowercase letters. 'Zebra' < 'apple' because 'Z' occupies code point U+005A (90) while 'a' occupies U+0061 (97). This can feel backwards if you expect human-language sorting, but for binary search, consistency matters more than cultural intuition.

In practice, I have seen more bugs from people assuming their language performs "human-style" comparison than from people who simply read the documentation and used whatever ordering the language provides. Know what your default comparator does, and you will be fine.

First, Sort: The Rule That Makes String Binary Search Reliable

Why Unsorted Strings Break Binary Search

The halving trick only works because the array is already ordered. If elements to the left of arr[mid] are not all smaller than arr[mid], the algorithm can discard the half that actually contains the target.

Consider an unsorted array: ['banana', 'date', 'apple', 'cherry'], searching for 'apple'.

low = 0, high = 3
mid = 1  ->  arr[1] = 'date'
'apple' < 'date'  ->  discard right half, high = 0

low = 0, high = 0
mid = 0  ->  arr[0] = 'banana'
'apple' < 'banana'  ->  discard right half, high = -1

loop exits, returns -1

The target sits at index 2, but the search never looked there. It narrowed to the left half, concluded the word was missing, and returned -1. Binary search does not scan; it jumps. Jumping requires reliable ordering.

Sorting a String Array in Python, Java, and JavaScript

Python has two main options. list.sort() sorts in place, while sorted(list) creates a new sorted list:

words = ["banana", "date", "apple", "cherry"]
words.sort()  # in-place, lexicographic by Unicode code point

Java's standard library provides Arrays.sort() for arrays and Collections.sort() for lists:

String[] words = {"banana", "date", "apple", "cherry"};
Arrays.sort(words);
// words is now {"apple", "banana", "cherry", "date"}

In JavaScript, arr.sort() sorts in place by converting every element to a string and comparing UTF-16 code units:

const words = ["banana", "date", "apple", "cherry"];
words.sort();
// words is now ['apple', 'banana', 'cherry', 'date']

A JavaScript trap worth remembering: the default sort is string-based even for numbers. [10, 9].sort() produces [10, 9], because the string "10" comes before "9". This surprises developers constantly, and it is exactly why you should always be explicit about the comparator you want.

Use the Same Comparator for Sorting and Searching

Here is the trap I have debugged more than once in production code: a developer sorts an array with a case-insensitive comparator so that "Apple" and "apple" sit next to each other, then runs a search that uses the default case-sensitive comparison. Binary search makes its branching decisions based on the array's actual order. When the search comparison disagrees with that order, the algorithm walks in the wrong direction and never recovers.

For example, in Java:

// Sorting uses case-insensitive order
Arrays.sort(words, String.CASE_INSENSITIVE_ORDER);

// Searching with case-sensitive compareTo can miss "Apple"
int index = Arrays.binarySearch(words, "apple"); // unreliable

The Java API documentation for Arrays.binarySearch spells out the expectation: the array must be sorted into ascending order according to the same comparator used for the search. When you sort with String.CASE_INSENSITIVE_ORDER, you must also pass String.CASE_INSENSITIVE_ORDER to binarySearch:

int index = Arrays.binarySearch(words, "apple", String.CASE_INSENSITIVE_ORDER);

The same principle applies in Python and JavaScript. Whatever rule you used to order the collection is the only rule you may use to search it.

Code It: Binary Search Strings in Python, Java, and JavaScript

Python Implementation: binary_search_strings()

def binary_search_strings(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

words = ["apple", "banana", "cherry", "date"]
print(binary_search_strings(words, "banana"))  # 1
print(binary_search_strings(words, "mango"))   # -1

Python's <, >, and == operators already compare strings lexicographically by Unicode code point, matching the order produced by list.sort(). No extra work is needed.

Java Implementation: Arrays.binarySearch and compareTo

For most real-world Java code, you do not need to hand-roll anything. Sort with Arrays.sort, then call Arrays.binarySearch:

String[] words = {"apple", "banana", "cherry", "date"};
Arrays.sort(words);
int index = Arrays.binarySearch(words, "banana");  // index is 1

One convention trips people up: when the target is absent, Arrays.binarySearch does not return -1. It returns -(insertionPoint) - 1, where insertionPoint is the position where the target would be inserted to keep the array sorted. Check for a negative value before treating the result as an index.

If you want to see the mechanics, a hand-rolled loop with compareTo is instructive:

int binarySearchStrings(String[] arr, String target) {
    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        int cmp = target.compareTo(arr[mid]);

        if (cmp == 0) {
            return mid;
        } else if (cmp < 0) {
            right = mid - 1;   // target is smaller, go left
        } else {
            left = mid + 1;    // target is larger, go right
        }
    }
    return -1;
}

JavaScript Implementation: Match localeCompare With the Sort Rule

If you need code-unit ordering, the simplest JavaScript loop uses the relational operators directly:

function binarySearchStrings(arr, target) {
    let left = 0, right = arr.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (target === arr[mid]) return mid;
        else if (target < arr[mid]) right = mid - 1;
        else left = mid + 1;
    }
    return -1;
}

const words = ['apple', 'banana', 'cherry', 'date'];
console.log(binarySearchStrings(words, 'banana')); // 1

For locale-aware ordering, use localeCompare — but only if you also sorted with localeCompare:

const words = ['apple', 'banana', 'Cherry', 'date'];
words.sort((a, b) => a.localeCompare(b));

function binarySearchStringsLocale(arr, target) {
    let left = 0, right = arr.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const cmp = target.localeCompare(arr[mid]);

        if (cmp === 0) return mid;
        else if (cmp < 0) right = mid - 1;
        else left = mid + 1;
    }
    return -1;
}

Mixing localeCompare with the default sort() is risky. The ordering rules can diverge in subtle ways, and binary search will silently fail when they do.

Complexity Analysis: String Comparisons Add a Hidden O(m) Cost

Time Complexity: O(log n) Rounds, O(m log n) String Work

Most complexity discussions of binary search stop at O(log n), silently assuming that every comparison takes constant time. That assumption holds for integers. It falls apart for strings.

A string comparison can inspect up to m characters before finding a difference, where m is the length of the strings being compared. Two long strings that share a long prefix require a long scan. In the worst case, searching a sorted array of n strings performs O(log n) iterations, each doing O(m) comparison work, for a total of O(m log n).

In back-of-the-envelope numbers, a dictionary of 100,000 words requires roughly 17 binary search iterations. A human-readable word averages a few characters, so the string overhead is negligible. But if you store URLs, log lines, or long identifiers, the O(m) factor stops being theoretical.

Space Complexity: O(1) for Iterative, O(log n) for Recursive

An iterative binary search uses a handful of integer variables, so auxiliary space is O(1). A recursive version can consume O(log n) stack frames before unwinding. And if you use Python's sorted() instead of list.sort(), you pay an extra O(n) space for the copied list. The difference matters on memory-constrained systems, where in-place sorting plus iterative search is the leaner combination.

Edge Cases and Variations: Case-Insensitive Binary Search on String Arrays

Empty Strings, Nulls, and Missing Targets

An empty string is the smallest possible string in all three languages. Searching for "" in ['', 'apple', 'banana'] should return index 0.

Nulls are a policy decision. In Java, calling compareTo on a null target throws a NullPointerException. In Python, comparing None with a string also raises. The safest approach is to validate inputs before searching: filter nulls out of the array or handle them explicitly in a custom comparator.

Missing targets are worth a design decision, too. A simple function returns -1. Java's Arrays.binarySearch returns -(insertionPoint) - 1, which encodes where the missing element would belong. That extra information is valuable when you are about to insert the target into the array.

During a code review last month, I caught a subtle bug in exactly this area: a developer checked if (index > 0) after calling Arrays.binarySearch. When the target was missing, the function returned a negative value that happened to be -1, so the check passed and the code treated a missing element as if it existed at index 0. The correct guard is if (index >= 0).

Duplicates: Searching for the First or Last Matching String

Standard binary search returns some matching index when duplicates exist, but not necessarily the first or last one. In ['a', 'b', 'b', 'b', 'c'], a search for 'b' might land on index 2.

If you need the first occurrence, one modification does the trick: when you find a match, record it as a candidate and keep searching the left half.

def binary_search_first(arr, target):
    left, right = 0, len(arr) - 1
    result = -1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            result = mid
            right = mid - 1  # keep looking to the left
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return result

words = ['a', 'b', 'b', 'b', 'c']
print(binary_search_first(words, 'b'))  # 1

For the last occurrence, flip the continuation direction: after recording the match, move left to mid + 1.

Custom Comparators and Unicode-Aware Ordering

When binary search accepts a comparator, every comparison must go through that comparator. In Java, Collections.binarySearch(list, key, comparator) pairs naturally with Collections.sort(list, comparator).

List<String> words = Arrays.asList("Apple", "apple", "Banana");
words.sort(String.CASE_INSENSITIVE_ORDER);
int index = Collections.binarySearch(words, "APPLE", String.CASE_INSENSITIVE_ORDER);
// index is 0 or 1, depending on insertion order; either way, it finds a match

For localized text, code-point order may not match human expectations. Java's Collator, JavaScript's Intl.Collator, and Python's locale-aware sorting all implement the Unicode Collation Algorithm, which handles accents, contractions, and language-specific sort rules. Use one of those if your users expect their own language's dictionary order rather than a programmer's code-point order.

Binary Search on Strings vs. Other String Search Algorithms

Four Terms That Are Easy to Mix Up

The phrase "binary search with strings" generates surprisingly noisy search results, because several distinct concepts share the same vocabulary. If you landed here after looking for one of the others, here is a quick map:

How to Tell Which Search You Actually Need

A quick decision guide:

• Repeated exact lookups in a static, sorted word list? Sort once, then binary search.
• Frequently changing data with exact lookups? A hash table gives O(1) average lookups; a balanced tree maintains order if you also need range queries.
• Pattern matching inside a single text value? Use substring search, not binary search. Binary search compares complete values; it cannot tell you whether a pattern occurs inside a word.

Frequently Asked Questions

Can you use binary search on strings?

Yes. The algorithm works on any data type that supports a total ordering. For strings, the list must be sorted lexicographically and the search must use the same ordering rule. Instead of comparing numbers with < and >, you compare strings with lexicographic operations: Python's relational operators, Java's compareTo, or JavaScript's localeCompare.

Do you need to sort strings before binary search?

Yes. Binary search's correctness depends on a sorted input. On an unsorted array, the algorithm can discard the half that contains the target and return -1 even when the value exists. Sorting strings lexicographically before calling binary search is not optional; it is the algorithm's contract.

How do you compare strings during a binary search?

Each iteration compares the target against the middle string. In Java, target.compareTo(names[mid]) returns a negative value if the target is smaller, zero if equal, and a positive value if larger. In JavaScript, target.localeCompare(names[mid]) follows the same convention. In Python, the operators <, >, and == handle it directly. Whichever comparison you use, it must match the comparator you used to sort.

What is a binary string example?

A binary string is a sequence containing only the characters 0 and 1. For example, "1010" is a binary string that represents the decimal number 10. It has nothing to do with running binary search on an array of strings; the confusion comes purely from the shared word "binary."

What is a string search algorithm?

It depends on what you mean by "search." Finding a whole word in a sorted list of strings is a job for binary search. Finding a pattern inside one longer text is a job for substring search algorithms such as Knuth-Morris-Pratt or Boyer-Moore. Many languages provide built-ins that cover the common cases: indexOf and includes search within a string, while binary search operates across a sorted collection.

How to search within a string?

Use built-in substring methods like indexOf, includes, or startsWith in your language. Binary search cannot answer "does this text contain this substring?" because substring matching does not produce a sorted ordering you can halve. Binary search answers a different question: "is this complete string present in this sorted collection?"

The Bottom Line

Binary search with strings requires three things: a list sorted under a well-defined ordering, a lexicographic comparison rule, and a comparator that stays consistent between the sort and the search. Get those right, and the algorithm behaves exactly as reliably as it does on integers.

Everything else is a matter of awareness. String comparisons carry a hidden O(m) cost that turns O(log n) into O(m log n). Nulls, empty strings, duplicates, and case conventions all deserve explicit decisions. And keeping "binary search on a string array" distinct from "binary strings," "substring search," and "binary search trees" will save you from searching for the wrong problem entirely.

Now, run the examples in this tutorial on a real word list. Then change one thing — sort case-insensitively, search for the first duplicate, or add a custom comparator — and see what breaks. That experiment will teach you more about binary search with strings than any blog post can.