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

￡神魔★判官ぃ 2023-10-15 17:09 12阅读 0赞

#### 文章目录 ####

*  循环写法：
 *  递归写法：

--------------------

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

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

--------------------

## 循环写法： ##

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;
            }

## 递归写法： ##

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;
            }
        }

--------------------

至此，结束。

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