二分查找----1.搜索插入位置

题目链接

/**

        以O(log n)的时间复杂度快速查找元素--->二分查找

        二分查找:

                不断将数组拆分为两个子区间,淘汰不可能出现结果的子区间、缩小查找范围,直至搜寻到结果

                定义left,right两指针处于数组两端,计算mid并读取对应值与目标值做比较,再做相应处理

                若 mid == target 得到结果直接返回即可

                若 mid < target 说明目标值在右半区,淘汰左半区迭代left,重新计算mid重复上述流程

                若 mid > target 说明目标值在左半区,淘汰右半区迭代right,重新计算mid重复上述流程

                二分查找的特性也可直接改写为递归

*/

class Solution {/**以O(log n)的时间复杂度快速查找元素--->二分查找二分查找:不断将数组拆分为两个子区间,淘汰不可能出现结果的子区间、缩小查找范围,直至搜寻到结果定义left,right两指针处于数组两端,计算mid并读取对应值与目标值做比较,再做相应处理若 mid == target 得到结果直接返回即可若 mid < target 说明目标值在右半区,淘汰左半区迭代left,重新计算mid重复上述流程若 mid > target 说明目标值在左半区,淘汰右半区迭代right,重新计算mid重复上述流程二分查找的特性也可直接改写为递归*/public int searchInsert(int[] nums, int target) {//双指针 置于数组有效部分两端int left = 0;int right = nums.length - 1;while(left <= right) {//计算mid 均分数组,依据条件缩小查找范围int mid = (left + right) / 2;//刚好位于中间,直接返回结果if(nums[mid] == target) {return mid;} //目标值在右半区,淘汰左半区else if(nums[mid] < target) {left = mid + 1;}//目标值在左半区,淘汰右半区else if(nums[mid] > target) {right = mid - 1;}}//若未搜寻到目标值,left即为应插入的位置return left;}
}