Binary search

Topic link: 704

Difficulty: Easy

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

Example 1:

Enter nums = [-1,0,3,5,9,12], target = 9; Description: 9 appears in NUMS with subscript 4Copy the code

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2; Output: -1; Explanation: 2 does not exist, so -1 is returnedCopy the code

Tip:

  1. You can assume that all elements in NUMS are not repeated;
  2. N will be between [1, 10000];
  3. Each element of nums will be between [-9999, 9999]

Given the ordered array search target value, we can think of a binary search algorithm. So, this is a test of proficiency in dichotomous algorithms.

Processing process:

Core ideas:

The core is evaluated on the boundary with middle,

Target > nums[middle], middle+1, right-1;

Target < nums[middle], left+1, middle

One thing to be aware of is the boundary problem, when there is no target value in the array, this will cause subscript overflow. So right is minus 1.

The code implementation is as follows:

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

Left + (right-left)/2 (right-left)/2 (right-left)/2 (right-left)/2

Topic link: 35

Difficulty: Easy

Title description:

Given a sorted 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, return the position where it will be inserted in order.

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

 

Example 1:

Enter: nums = [1,3,5,6], target = 5

Output: 2

Example 2:

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

Output: 1.

Example 3:

Enter: nums = [1,3,5,6], target = 7

Output: 4

Example 4:

Enter: nums = [1,3,5,6], target = 0

Output: 0

Example 5:

Enter: nums = [1], target = 0

Output: 0

Tip:

1 <= nums.length <= 104

-104 <= nums[i] <= 104

Nums is an ascending array of non-repeating elements

-104 <= target <= 104

Code implementation:

class Solution {
    public int searchInsert(int[] nums, int target) {
        int leftIndex = 0;
        int rightIndex = nums.length -1; // subscript overflow

        while(leftIndex <= rightIndex){
            int middle = leftIndex + (rightIndex -leftIndex)/2; // Prevent integer overflow

            if(target == nums[middle]){
                return middle;
            }else if(target > nums[middle]){
                leftIndex = middle + 1;
            }else if(target < nums[middle]){
                rightIndex = middle -1; }}// Handle four cases:
        // 1. Data is in array, return middle
        // 2. Target value before all array elements [0, -1]
        // 3. Insert target value into array [left, right] right + 1
        [left, right] right + 1

        return rightIndex + 1; }}Copy the code