#35.Search Insert Position
Problem statement
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n)
runtime complexity.
Example 1
Input: nums = [1,3,5,6], target = 5
Output: 2
Example 2
Input: nums = [1,3,5,6], target = 2
Output: 1
Example 3
Input: nums = [1,3,5,6], target = 7
Output: 4
Explanation
็ตฆๅฎไธๅๆๅบ้ฃๅๅไธๅ็ฎๆจๅผ๏ผๅ ถไธญ้ฃๅๅ ง็ๅ ็ด ไธ้่ค๏ผๅฆๆๅจ้ฃๅไธญๆพๅฐ็ฎๆจๅผๅ่ฟๅๅ ถ็ดขๅผ๏ผ่ฅ้ฃๅๅ งไธๅญๅจ็ฎๆจๅผ๏ผๅ่ฟๅๆ็ถๆๅ ฅไฝ็ฝฎ็็ดขๅผ
้ๅถ่งฃๆณ็ๆ้่ค้ๅบฆ็บ O(log n)
Solution
็ฑ้ก็ฎ็ตฆ็ๆฏๅทฒๆๅบ้ฃๅ๏ผๆฒๆๅคชๅคๆณๆณ๏ผ็ดๆฅไฝฟ็จไบๅๆๅฐๆณไพ่งฃ
public int SearchInsert(int[] nums, int target)
{
int left = 0, right = nums.Length - 1, mid;
while (left <= right)
{
mid = (left + right) / 2;
if (nums[mid] == target) return mid;
else if (target > nums[mid]) left = mid + 1;
else right = mid - 1;
}
return left;
}
Reference
Thanks for reading the article ๐ท ๐ป ๐ผ
If you like it, please don't hesitate to click heart button โค๏ธ
or click like on my Leetcode solution
or follow my GitHub โญ
or buy me a coffee โฌ๏ธ I'd appreciate it.
Top comments (0)