35. Search Insert Position

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

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int SearchInsert(vector<int>& nums, int target) {
        int pivot, left = 0, right = nums.size() - 1;
        while (left <= right) {
            pivot = left + (right - left) / 2;
            if (nums[pivot] == target)
                return pivot;
            if (target < nums[pivot])
                right = pivot - 1;
            else
                left = pivot + 1;
        }
        return left;
    }
}

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

/** * @param {number[]} nums
 * @param {number} target * @return {number}
 */var searchInsert = function(nums, target) {
  if (nums.indexOf(target) === -1) {    for (let i = 0; i <= nums.length; ) {
      if (nums[i] < target) {        i++;
      } else {          return i
      }    }
  } else {    return nums.indexOf(target);
  }};

class Solution:
    def searchInsert(self, nums, target):
        left = 0
        right = len(nums) - 1
        while left <= right:
            pivot = left + (right - left) // 2
            if nums[pivot] == target:
                return pivot
            if target < nums[pivot]:
                right = pivot - 1
            else:
                left = pivot + 1
        return left

func searchInsert(nums []int, target int) int {
    var pivot, left, right int = 0, 0, len(nums) - 1
    for left <= right {
        pivot = left + (right-left)/2
        if nums[pivot] == target {
            return pivot
        } else if target < nums[pivot] {
            right = pivot - 1
        } else {
            left = pivot + 1
        }
    }
    return left
}

Algorithm

Пример:

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

Output: 2

👨‍💻

Алгоритм:

1️⃣

Инициализируйте указатели left и right: left = 0, right = n - 1.

2️⃣

Пока left <= right:

Сравните средний элемент массива nums[pivot] с целевым значением target.

Если средний элемент является целевым, то есть target == nums[pivot]: верните pivot.

Если цель не найдена:

Если target < nums[pivot], продолжайте поиск в левом подмассиве. right = pivot - 1.

Иначе продолжайте поиск в правом подмассиве. left = pivot + 1.

3️⃣

Верните left.

😎