Problem 1 Implement The Binary Search (20pt) Write a function to perform binary search in an ascendingly (small to large) sorted integer array. The binary search function signature is defined in problem_1.h static int binary_search(const int *data, int length, int target); It takes an integer as the number to search, and returns the first index of the input value if found. -1 if target is not found. Why is -1 okay to be used as the indication of "nothing found"? For example: Searching 6 in array [1, 3, 6, 8, 9] should return 2 because number 6 appears at index 2. Searching 9 in array [1, 3, 6, 8, 9] should return 4. Searching 7 in array [1, 3, 6, 8, 9] should return -1 because 7 is not found in this array. Searching 6 in array [1, 3, 6, 6, 9] should return 2 because the first 6 appears at index 2. Tests are provided, but one of the marked tests needs some additional work to pass validation. Binary search will be discussed in class as part of the search problem. If you need help, here >>> is a good start. Note that binary search can be implemented with or without recursion. If you are comfortable with recursion already, feel free to use it. Otherwise for-loop would be just fine. In fact, which method do you think is faster? (you can answer this in your code as a comment if you want to) When the homework is done, your code should pass all the tests that come from with assignment. Fix The Tests (10pt) Tests are given for this task, however, one of the tests is missing something, and will fail (memory leak) even if your binary search is correct. This failure would definitely show up when a memtest is run. (Or later, when Nop the cat bot runs.) Grader bot Nop the cat greets 1 Run cat .github/workflows/graderbot.art 4 5 )) 6 -(((---(((-- Hello! I'm Nop. The grader bot cat. Inspecting the code now. Problem 2 (30pt) Bubble Sort Implement The Bubble Sort (30pt) Implement bubble sort for an integer array. If you need help with bubble sort, here >>> is a good start. Requirements: Sorted result is in ascending order, e.g. for input [3,1,4,0], output would be [0,1,3,4]. Use given tests as a manual. In-place, which means, O(1) space complexity. No additional memory of the size of the input array is allowed. If not sure, clarify with the teacher. When this homework is correctly done, all provided tests should pass. Problem 3 (30pt) Identify The Perfect Customers The purpose of this homework is to practice TDD (Test Driven Development). The Story (...that I made up to make this task less boring) A company called HoveringCar has a group of social media influecers to promote its products. Based on the followers of each influencer, HoveringCar can identify some potential customers to reach out to for further engagement. In this work, we are employing a simple algorithm to identify such customers. If a certain customer (identified by his/her name and age) has followed all the given influecers, then he/she is chosen as a pential customer if the age is less than or equal to 25. For example, consider the following scenario: Influencer x, followers {{name: a, age: 21}, {name:b, age: 23}, {name:m, age: 26} } Influencer y, followers {{name:b, age: 23}, {name:c, age: 31}, {name:d, age: 45}, {name:m, ag e: 26} } Influencer z, followers {{name:b, age: 23}, {name:m, age: 26} } Then the common follower between influencer x, y and z, hence the potential customer, is {name:b, age: 23}. z is not one because age does not meet requirements. Note: for simplicity, assume no overlap between followers and influencers. The related OOP classes are defined in problem_3.h, and the function that implements this algorithm is provided problem_3.cpp line #12. This means you do not need to implement the function, and better yet, you don't even need to look into this function to understand it. The Task "What do I do then?" You ask. In this task, come up with a set of tests for the problem of identifying potential customers based on the description above, without you writing the function code. The tests you write should interrogate the find_customer function to make sure it follows the algorithm correctly. Your tests should be written in "unit_test_problem_3.cpp". Note: Your tests should pass upon submission. If you think your test is correct but it fails, please reach out to the instructor immediately for a discussion. Connor has tested it too but who knows, he might have missed something.