二分查找8005算法c语言,寻找左侧边界的二分查找

寻找左侧边界的二分查找

```

int left_bound(int[] nums, int target) {

if (nums.length == 0) return -1;

int left = 0;

int right = nums.length; // 注意

while (left < right) { // 注意

int mid = left+(right-left)/ 2;//防溢出

if (nums[mid] == target) {

right = mid;

} else if (nums[mid] < target) {

left = mid + 1;

} else if (nums[mid] > target) {

right = mid; // 注意

}

}

return left;

}

```

细节改动与影响：

```

改动1：while (left < right)；

此时终止条件为left=right，搜索区间为[left,right)

```

```

改动2：if (nums[mid] == target) {

right = mid;

}

当搜索到target，不急于返回值，而是缩小搜索区间的商界right，在[left,mid)继续搜索，即不断向左侧收缩，以达到锁定左侧边界的目的。

```

```

改动3：else if (nums[mid] > target) {

right = mid; // 注意

}

当搜索到的值比target大时，缩小搜索区间为[left,mid)

```

```

改动4：return left;

为什么要返回left,而不是-1，其实是有意义的。

```

比如给二个数组[1,3,4,5,7,9,9,9,16,19]，[1,3,4,5,7,9,11,13,16,19]

用上面的算法做一个图解过程(搜索9为例)

具有重复元素的数组的图解过程：






不具有重复元素的数组的图解过程(同上，只是6,7位的元素不同而已)

```

此时返回值为5，说明比索引的数小的数有5个。如果搜索16的话，则会返回8，说明之前有8个数小于16.

这样又会有一个问题，如果搜索8的话，返回值为5，但是数组有没有这个数，该怎么办？

那就加一段补丁：

......

if(left==nums.length)reutrn -1;

return nums[left]==target?left:-1;

```

寻找右侧边界的二分搜索同理

应用变种：

1.查找第一个值等于目标值的元素或位置(左侧边界)

2.查找最后一个值等于目标值的元素或位置(右侧边界)

3.查找第一个大于等于目标值的元素(右侧边界)

4.查找最后一个小于等于目标值的元素(左侧边界)

适用环境：

1.适用于一次排序多次查找的场景中。

2.适用于单次比较非常耗时，需尽量减少比较次数的场景。

3.不适用于数据量太大的场景，因为二分查找需要连续内存。

0.0分

2 人评分