USE OF AI TOOLS IS NOT ALLOWED AS YOUR CODE WILL BE SUBMITTED TO MOSS $($AN AI CODE PLAGARISM TOOL$)$ AND ONCE AI IS DETECTED YOU WILL GET ZERO.

AFTER WRITING YOUR CODE PUSH YOUR CODE TO GITHUB AND PASTE THE LINK ON MOODLE, FAILURE TO DO THAT WILL RESULT IN YOU GEETING A ZERO.

Question

A company stores its products in a large warehouse. The products are indexed in a database with unique IDs. Normally, the product IDs are sorted in ascending order, but due to a recent system update, the database was rotated at an unknown index, causing the list of product IDs to become partially sorted.

For example, the original sorted list of product IDs might have been: $,106,107$

But after the rotation, the list looks like: $[104,105,106,107,101,102,103]$

Your task is to write an efficient algorithm using binary search that allows the company to quickly find the index of any product by its ID in this rotated database. If the product ID is not found, your algorithm should return $-1.$

Algorithm Implementation $(50$ Marks$)$

Write the Java method findProductIndex that takes in two arguments:

productIDs$[]$: a rotated sorted array of integers representing the product IDs in the warehouse.

targetID: an integer representing the product ID to search for.