w3resource

JavaScript - Ternary search algorithm

JavaScript Searching Algorithm: Exercise-3 with Solution

Write a JavaScript program to find the first index of a given element in an array using the ternary search algorithm.

A ternary search algorithm is a technique in computer science for finding the minimum or maximum of a unimodal function. A ternary search determines either that the minimum or maximum cannot be in the first third of the domain or that it cannot be in the last third of the domain, then repeats on the remaining two thirds. A ternary search is an example of a divide and conquer algorithm.

Test Data:
([1, 2, 3, 4, 5, 6, 7, 8, 9], 3, 0, 5)) -> 2
([1, 2, 3, 4, 5, 6, 7, 8, 9], 9, 0, 8)) -> 8
([1, 2, 3, 4, 5, 6, 7, 8, 9], 0, 0, 8)) -> -1
([1, 2, 3, 4, 5, 6, 7, 8, 9], 4, 6, 8)) -> -1

Sample Solution:

JavaScript Code:

const ternary_Search = (arr, target, left, right) => {
	if (right >= left) {
		let mid1 = Math.floor(left + (right - left) /3);
		let mid2 = Math.floor(right - (right - left) /3);

		if (arr[mid1] == target) {
			return mid1;
		}
		else if (arr[mid2] == target) {
			return mid2;
		}

		if (target < arr[mid1]) {
			return ternary_Search(arr, target, left, mid1 - 1);
		}
		else if (target > arr[mid2]) {
			return ternary_Search(arr, target, mid2 + 1, right);
		}
		else {
			return ternary_Search(arr, target, mid1 + 1, mid2 - 1);
		}
	}
	return -1;
}

console.log(ternary_Search([1, 2, 3, 4, 5, 6, 7, 8, 9], 3, 0, 5))
console.log(ternary_Search([1, 2, 3, 4, 5, 6, 7, 8, 9], 9, 0, 8))
console.log(ternary_Search([1, 2, 3, 4, 5, 6, 7, 8, 9], 0, 0, 8))
console.log(ternary_Search([1, 2, 3, 4, 5, 6, 7, 8, 9], 4, 6, 8))


Sample Output:

2
8
-1
-1

Flowchart:

Flowchart: JavaScript - Ternary search algorithm.

Live Demo:

See the Pen javascript-searching-algorithm-exercise-3 by w3resource (@w3resource) on CodePen.


* To run the code mouse over on Result panel and click on 'RERUN' button.*

Improve this sample solution and post your code through Disqus

Previous: Linear search algorithm.
Next: Jump search algorithm.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Share this Tutorial / Exercise on : Facebook and Twitter

JavaScript: Tips of the Day

function and arguments

const person = {
  name: 'Lydia Hallie',
  hobbies: ['coding'],
};

function addHobby(hobby, hobbies = person.hobbies) {
  hobbies.push(hobby);
  return hobbies;
}

addHobby('running', []);
addHobby('dancing');
addHobby('baking', person.hobbies);

console.log(person.hobbies);

The addHobby function receives two arguments, hobby and hobbies with the default value of the hobbies array on the person object.
First, we invoke the addHobby function, and pass "running" as the value for hobby and an empty array as the value for hobbies. Since we pass an empty array as the value for y, "running" gets added to this empty array.
Then, we invoke the addHobby function, and pass "dancing" as the value for hobby. We didn't pass a value for hobbies, so it gets the default value, the hobbies property on the person object. We push the hobby dancing to the person.hobbies array.
Last, we invoke the addHobby function, and pass "bdaking" as the value for hobby, and the person.hobbies array as the value for hobbies. We push the hobby baking to the person.hobbies array.
After pushing dancing and baking, the value of person.hobbies is ["coding", "dancing", "baking"]

Ref: https://bit.ly/2Hcpkm6