[LeetCode] Algorithm I - Day 1 Binary Search

Algorithm I - Day 1 Binary Search

In mathematics and computer science, an algorithm is defined as a process or set of rules to be followed in calculations or other problem-solving operations. This practical method is often used in calculations, data processing, and automatic reasoning because it contains clear and concise instructions and can be executed in limited time and space complexities.

---

704. Binary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

📖 문제. target이 배열안에 있으면 해당 인덱스를 반환합니다. 그렇지 않으면 -1을 반환합니다.
O(log n) 런타임 복잡도로 알고리즘을 작성해야 함

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length-1;
        
        while(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] == target){
                return mid;
            } 
            else if(target > nums[mid]) {
                left = mid + 1;
            }
            else{
                right = mid - 1;
            }        
        }
        return -1;
    }
}

---

278. First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example 1:

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

Example 2:

Input: n = 1, bad = 1
Output: 1

📖 문제. n개의 버전 [1, 2, ..., n] 중 첫 번째 잘못된 버전을 찾으시오.
버전 불량 여부를 반환하는 API bool is BadVersion(version)이 제공됩니다.

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1, right = n;
        
        while(left < right){
            int mid = left + (right - left) / 2;
            if(isBadVersion(mid)) right = mid;
            else left = mid+1;
        }
        return left;
    }
}

---

35. Search Insert Position

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7
Output: 4

 

Constraints:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums contains distinct values sorted in ascending order.
• -104 <= target <= 104

📖 문제. 오름차순 으로 정렬된 배열에 target 이 있으면 해당 인덱스 반환, 없으면 해당 숫자가 들어가야할 자리의 인덱스를 반환 하시오. O(log) 런타임 복잡성에 알고리즘을 사용해야 합니다.

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length-1;
 
        while(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] == target){
                return mid;
            }
            else if(target > nums[mid]){
                left = mid + 1;
            }
            else{
                right = mid - 1;
            }   
        }
        return left;
    }
}