Description
704. Binary Search
Easy
Topics
Companies
Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
Example 2:
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1
Constraints:
1 <= nums.length <= 10^4
-10^4 < nums[i], target < 10^4
All the integers in nums are unique.
nums is sorted in ascending order.
Answer and Explaining
int search(int* nums, int numsSize, int target) {
int left = 0; // 初始化左pointer,指向陣列的起始位置
int right = numsSize - 1; // 初始化右pointer,指向陣列的結束位置
// 當左pointer小於或等於右pointer時,繼續迴圈
while (left <= right) {
// 計算中間索引,使用 (right - left) / 2
int mid = left + (right - left) / 2;
// 如果中間值等於目標值,則返回中間索引
if (nums[mid] == target) {
return mid;
// 如果中間值小於目標值,則將左pointer移到中間索引的右邊
} else if (nums[mid] < target) {
left = mid + 1;
// 如果中間值大於目標值,則將右pointer移到中間索引的左邊
} else {
right = mid - 1;
}
}
return -1;
}
Testing
int search(int* nums, int numsSize, int target) {
int left = 0; // 初始化左pointer,指向陣列的起始位置
int right = numsSize - 1; // 初始化右pointer,指向陣列的結束位置
// 當左pointer小於或等於右pointer時,繼續迴圈
while (left <= right) {
// 計算中間索引,使用 (right - left) / 2
int mid = left + (right - left) / 2;
// 如果中間值等於目標值,則返回中間索引
if (nums[mid] == target) {
return mid;
// 如果中間值小於目標值,則將左pointer移到中間索引的右邊
} else if (nums[mid] < target) {
left = mid + 1;
// 如果中間值大於目標值,則將右pointer移到中間索引的左邊
} else {
right = mid - 1;
}
}
return -1;
}
#include <stdio.h>
int main() {
int nums[] = {-1, 0, 3, 5, 9, 12}; // 範例有序整數陣列
int target = 9; // 目標值
int numsSize = sizeof(nums) / sizeof(nums[0]); // 計算陣列的大小
// 呼叫二分搜尋函數並輸出結果
int result = search(nums, numsSize, target);
printf("目標值 %d 的索引為: %d\n", target, result); // 預期輸出: 目標值 9 的索引為: 4
return 0;
}