31 lines
938 B
TypeScript
31 lines
938 B
TypeScript
|
|
|
|
// Searching algorithm: Binary search
|
|
// Write function bSearch so that it return the location of target if
|
|
// it is found in array list. If target is not found bSearch returns -1
|
|
function bSearch(list: string[], target: string) {
|
|
let left = 0
|
|
let right = list.length - 1
|
|
|
|
while (left <= right) {
|
|
let mid = Math.floor((left + right) / 2)
|
|
if (list[mid] === target) {
|
|
return mid
|
|
}
|
|
if (list[mid]! < target) {
|
|
left = mid + 1
|
|
} else {
|
|
right = mid - 1
|
|
}
|
|
}
|
|
|
|
return -1
|
|
}
|
|
|
|
// use the following array to test your function
|
|
let arr = ["Allegator", "Bee", "Bull", "Dog", "Ferret", "Tiger", "Zebra"] // already sorted a-z
|
|
|
|
console.log("Zebra was at location " + bSearch(arr, "Zebra"))
|
|
console.log("Bee was at location " + bSearch(arr, "Bee"))
|
|
console.log("Allegator was at location " + bSearch(arr, "Allegator"))
|