请实现无重复数字的升序数组的二分查找
给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标（下标从 0 开始），否则返回 -1
C++代码：
#include <iostream>
using namespace std;
//数组以升序排列时，二分法查找target
int binSearch(int nums[], int n,int target)
{
int low, high, mid;
low = 0;
high = n - 1;
while (low <= high)
{
mid = (low + high) / 2;
if (target < nums[mid])
high = mid - 1;
else if (target > nums[mid])
low = mid + 1;
else
return mid;
}
return -1;
}
int main()
{
int i, target, pos;
int nums[10];
cout << "请输入10个整数（升序）:";
for (i = 0; i < 10; i++)
cin >> nums[i];
cout << "请输入要查找的数:";
cin >> target;
pos = binSearch(nums, 10,target);
if (pos < 0)
cout << "未找到此数";
else
cout << target <<"在数组中的下标为:" << pos;
return 0;
}
以下是一个实现了无重复数字的升序数组的二分查找的 Python 代码：
def binary_search(nums, target):
"""
在升序数组 nums 中查找目标值 target。
如果找到就返回下标，否则返回 -1。
"""
n = len(nums)
left, right = 0, n - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
在这个函数中，我们使用了标准的二分查找算法。算法思路是：设定左右两个指针（变量left和right），并计算它们的中点（变量mid），然后比较中点的值与目标值的大小关系，根据比较结果缩小搜索区间，最终找到目标值或者确定不存在。
由于已经说明了数组中元素是升序且无重复的，因此不必考虑元素重复或乱序的情况，只要按顺序进行二分查找即可。
请尝试是否解决了问题
def binary_search(nums, target):
left, right = 0, len(nums) - 1 # 初始化左右边界
while left <= right:
mid = (left + right) // 2 # 计算中间位置
if nums[mid] == target: # 目标值等于中间值，直接返回mid
return mid
elif nums[mid] > target: # 目标值可能在左边区间
right = mid - 1
else: # 目标值可能在右边区间
left = mid + 1
return -1 # 未找到目标值，返回-1
特别特别需要注意的一个地方，自己做题的时候就这个地方没有通过。即如果数组是int[] array = {1,2,2,3,4};我们查找元素为2的下标，因为2号元素也是2，所以返回的就是2，而不是我们想要的1，所以我们要把nums[mid] 和nums[mid - 1]做一个比较
else if(nums[mid] == target){
while(mid != 0 && nums[mid] == nums[mid - 1])
mid--;
return mid;
}
public class Main {
public static void main(String[] args) {
int[] array = {1,2,2,3,4};
System.out.println(search(array, 2));
}
public static int search (int[] nums, int target) {
if(nums == null || nums.length == 0){
return -1;
}
// write code here
int left = 0;
int right = nums.length-1;
while(left<=right){
int mid = (left+right)/2;
if(nums[mid]>target){
right = mid -1;
}else if(nums[mid]<target){
left = mid + 1;
}else if(nums[mid] == target){
while(mid != 0 && nums[mid] == nums[mid - 1])
mid--;
return mid;
}
}
return -1;
}
}
我可以回答该问题。
实现无重复数字的升序数组二分查找：
输入的参数要求是一个升序数组和要查找的数字。
需要返回该数字在数组中的下标，如果不存在返回-1。
具体的函数实现如下：
int BinarySearch(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
示例代码如下：
#include <iostream>
#include <vector>
using namespace std;
int BinarySearch(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
int main() {
vector<int> nums = {1, 2, 3, 4, 5, 6, 7};
int target = 4;
int index = BinarySearch(nums, target);
cout << index << endl;
return 0;
}
该代码实现了输入一个升序数组和一个要查找的数字，返回该数字在数组中的下标，如果不存在则返回-1。函数实现的思路是二分查找算法，时间复杂度为O(logn)。
def binary_search(nums, target):
def search(left, right):
if left > right:
return -1
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] > target:
return search(left, mid - 1)
else:
return search(mid + 1, right)
return search(0, len(nums) - 1)
nums = [1,2,3,5,7,9]
target = 7
print(binary_search(nums, target))
target = 4
print(binary_search(nums, target))