Binary Search

4 flashcards · Other · by Steven Bui

1. 374. Guess the Number You are supposed to guess someone's number, which is between 1 and n. You are already given an API (given below), which returns -1 if you guessed higher than the actual number, 1 if you guessed lower than the actual number, and 0 if you got it. Return the number. ex. Input: n = 10, and actual number = 6 Output: 6 ---------------------------------------------------------------------------------- public int method (int n) { .... } API: int guess (int num)

   Approach: Take a binary search approach. First, initialize 2 variables: low will be set to 1, and high will be set to n (since the number can include 1 and n). While low is less than or equal to high, get the middle number between low and high, and call guess() on that number. If guess() returns -1, then this means you guessed too high, so set the new high limit to mid - 1. If guess() returns 1, then this means you guessed too low, so set the new low limit to mid + 1. Do this until guess() retu…

2. 35. Find Target With Binary Search Given a sorted integer array nums and an integer target, return the index of the target if it exists, or the index of where the target would be inserted at if it does not exist. ex. nums = [1, 3, 5, 6], and target = 2 Output: 1 ---------------------------------------------------------------------------------- public int method (int[] nums, int target) { .... }

   Approach: Take a binary search approach. First, initialize 2 variables: left is at index 0, and right is at the last index. While left is less than or equal to high, get the middle index between left and right. If the target is at that index, return that index. If the number is LESS than the target, then change LEFT to be mid + 1. If the target is greater than the target, then change right to be mid - 1. Outside of the while loop, return the left index. Code: public int searchInsert(int[] nums,…

3. 74. Find Target in a 2D Matrix Given an m x n integer array matrix where each number is in increasing order from left to right and top to bottom, return true if a target value is in the matrix. ex. Output: true ---------------------------------------------------------------------------------- public boolean method (int[][] matrix, int target) { .... }

   Approach: Take a binary search approach. Treat the 2D matrix as a 1D matrix by setting left to index 0 and right to (rows * cols) - 1. Also set rows and cols variables. While left is less than or equal to right, get the middle index between left and right. You then get the value of this middle index by getting the value at matrix[mid / rows][mid % rows]. Then do regular binary search: If the number is LESS than the target, then change LEFT to be mid + 1. If the target is greater than the target…

4. 162. Find Peak Element Given an int array nums, return any index which contains a value that is greater than the 2 values next to it. For indices 0 and n-1, assume that the edge value next to it is smaller, so indices 0 and n-1 could be returned. ex. nums = [1, 2, 3, 1] Output: 2 (since index 2 has a peak) ---------------------------------------------------------------------------------- public int method (int[] nums) { .... }

   Approach: Take a binary search approach. The trick is to realize that if the middle index does not have a peak, then there must be a peak in either the left side or the right side. You will know if you are at a peak when the left index == right index (i.e. the middle index == left == right == a peak index). First, set initialize 2 variables: left at index 0, and right at index n-1. While left is less than right (NOT less than or equal too, since equals means at a peak), get the middle index. If…