Created
March 21, 2016 23:20
-
-
Save jianminchen/b4e6a00926b5db8138ea to your computer and use it in GitHub Desktop.
Two string - JavaScript - binary search tree, Math.round
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function processData(input) { | |
function parse(str) { | |
return parseInt(str, 10); | |
} | |
var lines = input.split('\n'); | |
var length = parse(lines.shift()); | |
for (var i = 0; i < length; i++) { | |
console.log(testCase(lines)); | |
} | |
} | |
function testCase(lines) { | |
var a = lines.shift(); | |
var b = lines.shift(); | |
for (var i = 0; i < a.length; i++) { | |
var char = a.charAt(i); | |
if (binarySearch(b, char, 0, b.length - 1)) { | |
return 'YES'; | |
} | |
} | |
return 'NO'; | |
} | |
function binarySearch(str, char, start, end) { | |
if (start > end) { | |
return false; | |
} | |
var middle = Math.round((start + end) / 2); | |
var midValue = str.charAt(middle); | |
if (midValue === char) { | |
return true; | |
} | |
if (char > midValue) { | |
return binarySearch(str, char, middle + 1, end); | |
} | |
else { | |
return binarySearch(str, char, start, middle - 1); | |
} | |
} | |
process.stdin.resume(); | |
process.stdin.setEncoding("ascii"); | |
_input = ""; | |
process.stdin.on("data", function (input) { | |
_input += input; | |
}); | |
process.stdin.on("end", function () { | |
processData(_input); | |
}); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment