On Binary Search

Binary Search is a powerful technique in algorithms, used to cut down search space in pretty much constant time. A binary search against a space of 2^100 items takes a mere 100 iterations, again near constant time. When the breakthrough paper "Primes is in P" came out in 2003, it allowed primality test in logN time, exactly the calculation I showed above.

Problem below exemplifies the use of binary search. Find the indexes of the words, and perform binary search. Some calculation is needed to take into account the surrounding indexes, but other than that, straightforward. Code is down below, cheers, ACC.

Shortest Word Distance III - LeetCode

245. Shortest Word Distance III

Medium

Given an array of strings wordsDict and two strings that already exist in the array word1 and word2, return the shortest distance between the occurrence of these two words in the list.

Note that word1 and word2 may be the same. It is guaranteed that they represent two individual words in the list.

 

Example 1:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
Output: 1

Example 2:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "makes"
Output: 3

 

Constraints:

• 1 <= wordsDict.length <= 105
• 1 <= wordsDict[i].length <= 10
• wordsDict[i] consists of lowercase English letters.
• word1 and word2 are in wordsDict.

public int ShortestWordDistance(string[] wordsDict, string word1, string word2)
{
    List positionsWord1 = new List();
    List positionsWord2 = new List();

    for (int i = 0; i < wordsDict.Length; i++)
    {
        if (wordsDict[i].Equals(word1)) positionsWord1.Add(i);
        if (wordsDict[i].Equals(word2)) positionsWord2.Add(i);
    }

    int retVal = Int32.MaxValue;
    for (int i = 0; i < positionsWord1.Count; i++)
        retVal = Math.Min(retVal, ShortestWordDistanceBinarySearch(positionsWord1[i], positionsWord2));

    return retVal;
}

public int ShortestWordDistanceBinarySearch(int index1, List list2)
{
    int left = 0;
    int right = list2.Count - 1;

    while (left < right)
    {
        int mid = (left + right) / 2;
        if (list2[mid] == index1)
        {
            left = mid;
            break;
        }
        else if (list2[mid] > index1) right = mid - 1;
        else left = mid + 1;
    }

    //Check surroundings
    int min = Math.Abs(list2[left] - index1) == 0 ? Int32.MaxValue : Math.Abs(list2[left] - index1);
    if (left + 1 < list2.Count) min = Math.Min(min, Math.Abs(list2[left + 1] - index1));
    if(left - 1 >= 0) min = Math.Min(min, Math.Abs(list2[left - 1] - index1));
    return min;
}