This is the 14th day of my participation in the August Text Challenge.More challenges in August

The title

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.

An algorithm of O(logn) time complexity must be used.

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

Analysis of the

From the topic analysis has several key points, comprehensive analysis using binary search method is the most appropriate.

  • An ascending sorted array
  • No repetition of elements
  • Arrays have at least one element and up to 1000 elements
  • The time complexity must be order logn.

Violence law

Regardless of algorithmic performance requirements, there is a violent solution to every problem, which is the most common one for us, which is to go through all the elements in the array until we find one that is greater than or equal to the value we are looking for.

package com.chenpi; Public class SearchInsert {public int SearchInsert (int[] nums, int target) {for (int I = 0; i < nums.length; I ++) {if (nums[I] >= target) {if (nums[I] >= target) {return I; }} return nums.length; return nums.length; } public static void main(String[] args) { SearchInsert inst = new SearchInsert(); int[] nums = {1, 3, 5, 6}; System.out.println(inst.searchInsert(nums, 5)); }}Copy the code

dichotomy

The system requires order logn, and the array is ordered, so binary search is the best way to do it.

package com.chenpi; Public class SearchInsert {public int searchInsert(int[] nums, int target) { int left = 0; int right = nums.length - 1; While (left + right)/2 int middle = left + ((right-left)/2); If (nums[middle] > target) {// Right = middle - 1; } else if (nums[middle] < target) {left = middle + 1; } else {return middle; } } return right + 1; } public static void main(String[] args) { SearchInsert inst = new SearchInsert(); int[] nums = {1, 3, 5, 6}; System.out.println(inst.searchInsert(nums, 5)); }}Copy the code

I am Chen PI, an ITer in Internet Coding. Search “Chen PI’s JavaLib” in wechat to read the latest articles in the first time oh!

This is the end of sharing ~~

If you feel that the article is helpful to you, like, favorites, attention, comment, your support is the biggest motivation for my creation!