算法设计与分析学习笔记之二分查找算法

---

二分查找只适用于有序的顺序表，非严格递增或是非严格递减都行。

二分查找运用到了分治的思想，将整体逐渐分为许多个小的部分，让整体的解变为诸多小部分解的合成，要求整体可以分解，小部分的解汇合之后可以得到整体部分的解。

---

循环写法：

int binarySearch(int[] array, int n, int searchNum) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            // 找出中间下标 
            int mid = low + ((high - low) >> 1);
            // 每次都设置所求区间的中间位置，和中间位置的数字作比较
            // (high - low) >> 1中的>>是右移运算符，等于'/2'
            if (nums[mid] > search_num) {
                high = mid - 1;
            } else if (nums[mid] < search_num) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

递归写法：

int recursiveBserach(int[] nums, int low, int high, int value) {
        if (low > high) return -1;
        // 每次都设置所求区间的中间位置，和中间位置的数字作比较
        int mid = low + ((high - low) >> 1);
 		// (high - low) >> 1中的>>是右移运算符，等于'/2'
		if (nums[mid] > search_num) {
            return recursiveBserach(nums, low, mid - 1, value);
        } else if (nums[mid] < search_num) {
            return recursiveBserach(nums, mid + 1, high, value);
        } else {
            return mid;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

---

至此，结束。

如果你觉得这篇文章写的不错，多多点赞~收藏吧！