35. Search insertion position

Given a sort array and a target value, find the target value in the array and return its index. If the target value does not exist in the array, returns the position where it will be inserted in order.

You must use an algorithm with a time complexity of O(log n).

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

Input: num = [1,3,5,6], target = 0
Output: 0

Example 5:

Input: num = [1], target = 0
Output: 0

Tips:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums Arranges the array in ascending order without repeating elements
-104 <= target <= 104

Problem solution

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

278. First wrong version

You are a product manager and are currently leading a team to develop new products. Unfortunately, the latest version of your product has not passed the quality test. Since each version is developed based on the previous version, all versions after the wrong version are wrong.

Suppose you have n versions [1, 2,..., n], you want to find the first wrong version that causes errors in all subsequent versions.

You can call the bool isBadVersion(version) interface to determine whether the version number is wrong in the unit test. Implement a function to find the first wrong 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
So, 4 is the first wrong version.

Example 2:

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

Tips:

1 <= bad <= n <= 231 - 1

Problem solution

 public int firstBadVersion(int n) {
        int left = 1;
        int right = n;
        while(left < right){//Cycle to equal left and right
            int mid = (right-left)/2 + left;//Prevent overflow and take median
            if(isBadVersion(mid)){//Determine whether it is the wrong version
                right = mid ;//Is the wrong version, i.e. [left,mid]
            }else{
                left = mid +1;//Not the wrong version, i.e. [mid,right]
            }
        }
        //The last left right is a point, that is, the first wrong version
        return left;
    }

704. Binary search

Given an n-element ordered (ascending) integer array nums and a target value target, write a function to search the target in nums. If the target value exists, return the subscript, otherwise return - 1.

Example 1:

Input: num = [- 1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 appears in nums and the subscript is 4

Example 2:

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

Tips:

You can assume nums All elements in are not repeated.
n Will be in [1, 10000]between.
nums Each element of will be [-9999, 9999]between.

Problem solution

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