CODEWITHSUNDEEP
javascriptalgorithm
Muhammad Umer
Muhammad Umer

Reputation: 2308

Can you do binary search in array of strings in javascript

I am trying to make a word look up thing. Problem there are thousands of words. It would be nice to this:

Search for first letter only, character at index 0, in array, get the index of key/value the ones which have and than search for, character at index 1, and so on.

what i don't want to do if possible...

Go to array[i], take its whole value, than find char at index 0, than say yes it is this or not. That kind beats the whole point. If am accessing the whole string so why not just evaluate the whole thing while at it.

Maybe i need to restructure the array somewhat differently. so main array would be like `var a = [a,b,c,...] then a[a]=[a,b,c,d,e,...] then so on eventually a[i][r][p][l][a][n][e]... maybe this is more efficient. It might be the only way possible if i can't access value's only first char in array without first taking in the whole thing than analyzing.

Upvotes: 1

Views: 3216

Answers (2)

tst
tst

Reputation: 667

Maybe I don't understand what you are trying to do, but if you can keep your word list sorted, then binary search is the quickest and most efficient way to do it:

function binarySearch(list, key) {
    let indexLow = 0;
    let indexHigh = list.length - 1;
    while (indexLow <= indexHigh) {
        const mid = Math.floor((indexLow + indexHigh) / 2)
        const x = list[mid]
        if (x === key) {
            return mid;
        }
        if (x > key) {
            indexHigh = mid - 1;
        } else {
            indexLow = mid + 1;
        }
    }
    return -1;
}

Upvotes: 0

Niklas
Niklas

Reputation: 25463

I think you can do it. You just have to sort the string array and maybe you can compare them with the char value for instance 65 for A.

I have not testet it, but this seems legit: http://www.dweebd.com/javascript/binary-search-an-array-in-javascript/

Upvotes: 2

Related Questions