Likou 35 - search for insertion position - binary search

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, returns the position where it will be inserted in order.

Please use an O(log n) algorithm.

Solution ideas

• This is also a question of finding elements, the title requirement is to find elements in an ordered array and return the index;
• If the element is not in the array, it should return its index position;

• 

• Then the target value may have four cases: ① It is smaller than the first element and placed at the front of the array; ② It is larger than the last element and inserted at the end of the array; ③ It is equal to a value in the array, and returnsIndex; ④ The value is not found in the array, find a suitable position to insert it
• It is conceivable that this kind of problem should be solved by the dichotomy method;
• At the beginning, judge the size relationship between target and the first and last elements of the array, and return the correct index;
• Use the left and right closed interval [ left , right ] in the search process;
• Just after judging all the cases, it should not return -1, it should return right+1, because right+1 is the index of the position to be inserted at this time.

Input and output example

Code

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