Python Coding Test Course, Dictionary Search

Problem Description

A person wants to find a word in a dictionary. This dictionary contains words sorted in alphabetical order. Write a program to find the first occurrence of a given word in the dictionary.

The input consists of a sorted list of words and the word to be searched. If the word does not exist in the dictionary, return -1.

Input Format

  • List of words: words (in list form, each word as a string)
  • The word to search for: target (string)

Output Format

Return the index of the word to be searched (0-based index). If the word does not exist, return -1.

Example

    Input: 
    words = ["apple", "banana", "cherry", "date", "fig", "grape"]
    target = "cherry"

    Output: 2

Approach to the Problem

This problem can be solved using the Binary Search algorithm. Binary search is an efficient algorithm for finding a specific value in sorted data, with a time complexity of O(log n).

Overview of the Binary Search Algorithm

Binary search proceeds as follows:

  1. Find the middle element of the list.
  2. Check if the middle element matches the value being searched for.
  3. If it matches, return the index of the middle element.
  4. If it does not match, continue searching in the left part if the value to be searched is smaller than the middle element, or in the right part if it is larger.
  5. Repeat this process until the condition is satisfied.

Implementation

Here we will implement the binary search algorithm using Python. Below is the dictionary-finding function using binary search.

def binary_search(words, target):
    left, right = 0, len(words) - 1

    while left <= right:
        mid = (left + right) // 2
        if words[mid] == target:
            return mid
        elif words[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Code Explanation

The above binary_search function operates as follows:

  1. Use left and right variables to set the search range. The initial values are 0 and len(words) - 1, respectively.
  2. Using the while left <= right loop, repeat until the search range is valid.
  3. Calculate the middle index mid (through integer division).
  4. If words[mid] is equal to target, return mid to return the index.
  5. If not, update left to mid + 1 if words[mid] is less than target, or update right to mid - 1 if it is larger.
  6. If the search ends without finding the target word, return -1.

Test Cases

Let’s add a few cases to test the functionality of the code.

if __name__ == "__main__":
    words = ["apple", "banana", "cherry", "date", "fig", "grape"]
    target = "cherry"
    result = binary_search(words, target)
    print(f"'{target}' is at index {result}.")  # Output: 'cherry' is at index 2.

    target = "orange"
    result = binary_search(words, target)
    print(f"'{target}' is at index {result}.")  # Output: 'orange' is at index -1.

Conclusion

In this lesson, we solved the problem of finding a specific word in a given dictionary using Python’s binary search algorithm. This algorithm is useful for quickly finding values in a sorted list and can be applied to various problems. Understanding and utilizing binary search is highly beneficial for coding tests and real programming tasks.

References